基于全同态加密的安全多方计算协议*

涂 航

（海军参谋部，北京 100841）

0 引言

随着云计算技术的飞速发展，越来越多的用户将个人数据上传至云服务器中交由云服务商管理，云服务商也将很多传统上本地化的服务提供给用户。智能信息化为当今社会提供便捷的环境的同时，如用户隐私泄露、网络攻击等安全问题却与日俱增。用户在很多云计算使用环境中并不希望其他用户和云服务商获得自己的个人信息，这正是安全多方计算（Secure Multi-party Computing，SMC）能解决的问题。

安全多方计算最早是由文献[1]通过百万富翁问题提出的，该研究描述的是两个参与者在不泄露自身信息的条件下进行比较，而在后续的研究中，参与者拓宽为多个。因此，安全多方计算就可以定义为，多个参与者在各自输入独立的情况下，共同进行一种运算。文献[2]将特定运算提高为任意代数运算，并给出协议的完整流程。文献[3]在对前人研究进行概括的基础上形式化地定义了安全多方计算的安全模型。文献[4]提出了参与者也有可能是攻击者的概念，将参与者根据行为定义为诚实参与者、半诚实参与者和恶意参与者。文献[5]在文献[4]提出的参与者类型上，论述了即使参与者有恶意的行为，依然可以通过完善的设计保护系统和其他参与者。

经过学界专家学者们多年的研究，安全多方计算已经有了长足的发展。目前，由于全同态加密算法可以解决云计算、大数据环境下的用户数据隐私保护问题，因此将全同态加密（Fully Homomorphic Encryption，FHE）算法与安全多方计算结合是一个新的研究热点。第一次真正意义上实现全同态加密算法的研究是Gentry 于2009 年发表的博士论文[6]，该论文提出了基于ideal latte的全同态加密算法。文献[7]利用门限加密与全同态加密相结合的构想，实现了文献[1]提出的两方比较问题的同态思路，并且将计算复杂度降低至O(m)（m为信息长度）。文献[8]基于格上容错学习（Learning With Error，LWE）的困难性假设，利用同态加密的思想，不直接比较输入是否相同，而是比较对输入的密文是否有映射关系来判断安全两方协议的正确性。

针对云计算的发展速度和安全多方计算实际部署问题，又有许多专家学者将服务器作为第三方来进行安全多方计算[9-12]。文献[9]充分利用云计算的特点，构造出一种在服务器上利用求参与者之间输入的最大近似公因子求解问题来进行判断安全多方计算的正确性。虽然该方案降低了参与者的计算需要；但是求解最大近似公因子本身需要的计算开销很大，如果参与者数量很多的情况下，就要求服务器拥有很大的计算能力。文献[10]利用多编码技术和部分同态加密部署在云服务上达到安全多方计算的目的，但是该方案不能抵抗合谋攻击，且计算开销较大。文献[11]将全同态加密算法转化为多比特并行加密，构造出困难性基于LWE的多比特全同态加密安全多方计算方案。文献[12]在文献[11]的基础上设计了一个困难性基于Ferr-LWE 和Someare-errorless-LWE的三轮协议的多方计算协议，该协议较好地控制了密文的膨胀，且其计算复杂度和密文膨胀率的控制是目前较好的。

充分考虑到实用性和安全性，本文首先决定采用整数上的全同态加密算法来构造一个由服务器作为第三方的安全多方计算协议。该协议需要参与者使用全同态加密算法预处理输入信息，服务器作为第三方只能对参与者的密文进行处理，保证了所有参与者的隐私不被泄露。

1 算法概述

1.1 相关定义

本文的符号及其代表的含义如表1 所示。

表1 符号对应表

有如下两个定义：

（1）Bχ-有界分布

有Bχ∈Z+，并有{χn}n∈N满足：

式中：{χn}n∈N是基于整数集的分布序列；negl(n)是一个可忽略函数。则称Bχ是有界的。

根据Bχ有界分布的定理，可以有推论：设Bχ有界分布中有服从的ei(i∈[N])的独立随机变量，其变化出的同样服从Bχ有界分布。

（2）稀疏子集求和问题

一个整数集合Z={x1,x2,…,xn}中的子集S={1,2,…,n}，找到一个S中的元素si(1 ≤i≤n)，使得i∈∑si·xi=0 是计算困难的。

1.2 全同态加密算法

全同态加密算法一般是由密钥生成算法、同态加密算法、同态解密算法和同态计算算法组成，分别记为：KeyGen、Homo.Enc、Homo.Dec、Evaluate。

（1）密钥生成算法（KeyGen）：随机选择一个参数，输出公私钥对(pk,sk)。

（2）同态加密算法（Homo.Enc）：对于全同态加密算法输入的明文m利用pk加密变成密文c的过程。

（3）同态解密算法（Homo.Dec）：对于Homo.Enc中产生的c利用sk还原回m的过程。

（4）同态计算算法（Evaluate）：对于多个密文c1,c2,…,cn，利用公钥pk执行一个任意的代数运算f的过程。

1.3 基于整数全同态加密算法

基于整数的全同态加密算法一般的安全性是基于近似最大公因子问题，本文采用的参数选择与文献[13]相同，同时给出整数上的全同态加密算法。一个全同态加密算法包含密钥生成算法、加密算法、解密算法和同态计算算法。

（1）密钥生成算法（KeyGen）：在密钥生成中心产生一个长度为η的素数集pi,j(1 ≤i,j≤μ)，μ为选定的参数用于确定明文空间。选择参数α定义为素数集中两个元素的乘积，随机选取一个元素β←Z∩[0,2γ/α]，并令β<2λ2，同时有γ=α·β。利用Bχ有界分布确定一个整数集合X，其界限为β，其中的元素为xi。再随机选取一个δ比特的奇正整数y，即。令公钥pk=〈x1,x2,…,xβ〉，私钥sk=y。

（2）同态加密算法（Homo.Enc）：首先以输入的明文为0 得到的密文组成集合C⊆ {1 ,2,…,β}；其次取r∈(-2β,2β)∩Z，计算c←m+2r+，S为1.1 小节中定义的稀疏子集求和中的子集S。

（3）同态解密算法（Homo.Dec）：计 算m←(cmodp)mod 2。

（4）同态计算算法（Evaluate）：通过公式计算Evaluate(pk,C,c1,…,ct)，其中t为电路C的输入。

1.4 安全多方计算模型

一个安全多方计算的模型为有n个参与者P={P1,P2,…,Pn}，参与者共同使用f(·)对输入xi(i=1,2,…,n)进行计算，得到一个计算结果y，并且参与者对于其他参与者的输入并不知情，如图1所示。

图1 安全多方计算模型

一般在模型中执行协议的操作步骤，并且不去获取其他参与者输入信息的参与者被称为诚实参与者。然而，在实际的应用场景中并不是所有的参与者都是“安分守己”的，有一些参与者虽然会执行协议的步骤，但是同时也会通过各种方法刺探其他参与者的输入信息，将这种参与者称为半诚实参与者。还存在一种参与者，他们不仅不会正常执行协议的步骤，而且还可能向协议无关者泄露协议执行中获得的信息，甚至破坏协议的运行，将这种参与者称为恶意参与者。模型中的攻击者用A来表示，攻击者一般是一个或多个参与者，故有A⊆2p。虽然半诚实的参与者不会主动对协议发起攻击，但是也存在着半诚实的参与者被收买等情况，所以在很多研究中除了将恶意参与者看作是攻击者，也将半诚实参与者看为攻击者。

2 基于整数全同态加密技术的安全多方计算协议

研究安全多方计算协议，需要考虑到实际网络类型、信道模式以及敌手攻击等问题。为了便于讨论，本文中约定网络类型为同步网络，即参与者之间不存在异步时钟，且信道模式为可信的安全信道，敌手为半诚实的参与者，同时有一个服务器充当第三方作为计算中心。本文设计的协议模型架构如图2 所示。

图2 基于整数全同态加密技术的安全多方计算协议

设基于整数全同态加密技术的安全多方计算协议中有n个参与者P={P1,P2,…,Pn}，分别持有各自的输入xi(i=1,2,…,n)，经过服务器计算后再得到处理后的信息(y´1,y´2,…,y´n)。由于全同态加密的性质，可以将(y´1,y´2,…,y´n)还原为安全多方计算的结果y。具体流程如图3 所示。

图3 基于同态加密的多方安全计算流程

具体的流程为分为4 步，如下文所述。

（1）初始化流程：参与方P1,P2,…,Pn使用密钥生成算法KeyGen(·)计算公私钥对(pk,sk)(i=1,2,…,n)。

（2）加密处理流程：参与方P1,P2,…,Pn分别将各自的输入xi(i=1,2,…,n)使用全同态加密算法Homo.Enc进行加密，得到各自的密文ci→Homo.Enc(xi)，并将其发送给服务器。

（3）安全多方计算流程：服务器接收到各个参与者发送到的密文ci后，使用安全多方计算协议进行处理，得到y→f(c1,c2,…,ci)。

（4）同态计算流程：服务器在对安全多方计算流程中计算的结果进行同态计算得到Eval(y´)→(y´1,y´2,…,y´n)，并将结果返还给各个参与者。

经过上述4 个步骤，参与者将各自输入的密文上传至服务器进行安全多方计算处理，从服务器得到返回的计算结果。整个过程中服务器并不知道参与者的原始输入，只能对参与者上传的密文进行处理。这样能保证其他参与者和服务器并不知道其原始输入信息，从而保护了各个参与者的隐私。

3 结语

本文基于整数上的全同态加密算法构造了一个安全多方计算协议，该协议约定网络类型为同步网络，信道模式为可信的安全信道，敌手为半诚实的参与者。该协议分为4 个步骤，充分利用了全同态加密的性质，所有的参与者所得到的只有经过服务器处理后的对应输入的信息，同时该协议构造简洁，只需要两轮通信。

本文提出协议仍有需要改进的地方。由于全同态加密需要较大的计算能力，因此协议是将这部分交由参与者处理，这时如果有恶意的参与者混入其中，则最后可能无法还原回安全多方计算过程得到的结果。后续研究工作中将针对这一问题进一步完善该协议。