云计算通过网络将大量的存储资源、计算资源及软件资源链接在一起,形成资源池,给我们带来了超强的计算能力、无限的存储能力和巨大的经济效益,为广大计算机用户提供高效、便捷的服务.云计算已经成为信息领域关注的热点问题,各国都给予了高度的关注.但利用云进行计算或存储需要把数据交给云,这对参与者计算的数据安全性与隐私构成了巨大的威胁,使得云计算的安全问题成为学术界及工业界关注的焦点^[1],也是广大用户是否使用云计算的决定性因素.

多方保密计算(secure multipaty computation)是网络空间安全与隐私保护的关键技术,具有广泛的应用,但往往需要进行计算量比较大的公钥加密运算,数据较多的时候对很多用户都是一个难题.研究利用云计算平台完成这样的计算,同时又保护用户的隐私,对云计算的推广普及和云计算中的隐私保护都有重要的理论与实际意义.本文是这方面工作的有益探索.

多方保密计算最早由姚期智教授^[2]提出,是指多个参与者联合进行的秘密计算,计算结束后,每个参与者除了计算结果外,其输入信息没有任何泄露.随后,Goldreich等人^{[3, 4]}从理论上证明了任意的多方保密计算问题都是可解的,并给出了通用的解决方案.但同时指出,从计算效率方面考虑对具体的问题应该研究具体的解决方案.这使得人们纷纷研究各种各样多方保密计算问题的解决方案,如百万富翁问题^{[5, 6]}、保密计算几何^[7]、保密的信息比较^[8]、保密的集合问题^[9]、保密的远程访问^[10]、保密拍卖^[11]、保密的数据挖掘^[12]等.Goldreich等人还设计了一个编译器,借助于该编译器,可以用一个对于半诚实(semi-honest)参与者安全的多方保密计算协议生成一个对于恶意(malicious)参与者也安全的多方保密计算协议.这一成果也体现了研究半诚实模型下的多方保密计算协议的价值,Goldreich在文献[4]中专门论述了研究半诚实模型下多方保密计算的理论与实际意义.

集合是一个非常重要的概念,现实中的很多问题都可以用集合表示,集合问题的研究是多方保密计算研究的一个重要方面.现有的关于保密计算集合问题的研究包括保密计算集合的交集^[13-16]、保密计算集合的并集^[17-21]以及保密计算集合交集与并集的势^{[22, 23]}等,但这些研究多是基于两个参与者的情况,对于多个参与者的研究还比较少,且计算效率较低.

Freedman^[13]首先给出了多个参与者集合交集的保密计算方案,该方案借助于Paillier公钥加密算法,同时利用多项式不经意求值的方法给出了解决方案,但该方案需要对每个参与者的多项式系数加密,然后通过对加密后的多项式计算来实现集合交集的保密计算,计算复杂性与通信复杂性都很高,效率很低,且所有集合的元素都来自一个无限大的范围.Kissner^[17],Frikken^[18]给出的多个集合并集的保密计算方案,将每个参与者的集合表示成多项式的形式,然后利用多项式的数学性质与同态加密算法给出了具体的解决方案.但他们需要借助混合网或将元素混淆来计算所有集合的并集,计算复杂性较高,并且计算的结果不是真正的交集或者并集,而是一个多重集,泄露了较多的信息.文献[19]通过对所有参与者集合中的元素进行不经意排序,根据排序结果得到多个集合并集的计算结果,但该方法中的不经意排序主要是借助于文献[24]中电路的方法实现的.

基于电路的方法虽然高效,但也存在电路相关的一些缺点.

· 首先,一个简单的算法用电路实现也很困难,转换成的电路的规模也是惊人的,存储这样的电路会很快消耗完计算机的所有内存资源^[25];

· 此外,电路方法的可移植性与普遍适用性较差,需要预先估计要计算集合元素的范围,从而推算出可能需要的比较门(gate)的数量及电路的深度,超出预定范围的对象将不能进行计算,需要根据具体的应用场景设计相应的电路,不具有普遍适用性.

文献[20]将参与者的集合表示成多项式的形式,并利用翻转罗朗级数(reversed Laurent series)和秘密共享的方法给出了集合并集的保密计算方案.文献[21]借助全同态加密算法和多项式求值的方法给出的方案只能计算集合的并集,方案的通信轮数是参与者个数的线性函数,但方案的计算复杂性仍然很高,效率较低.以上的这些方案均不能借助于半可信的云服务器完成集合的保密计算,参与者的计算量都是很大的.

本文研究的集合隐私计算问题是指多个参与者在云计算环境下的集合并集与交集的保密计算问题,由于云平台中运行的各类云应用没有固定不变的基础设施和安全边界,难以实现参与者的数据安全与隐私保护,因此需要参与者利用密码学的方法来实现安全的云计算.根据多方保密云计算^[26]的思想,将云看做是由多个云服务器组成的集合,云上的计算看作多个云服务器间的计算.借助于新的编码方法,将每个参与者的集合用一个相应的向量替代,根据新向量的计算结果可以得到原有集合的计算结果.该方案可以用乘法同态加密算法构造,也可以用加法同态加密算法构造,具有普遍的适用性.同时,该方案也可以借助于一个半可信的云服务器实现隐私的集合计算.

利用哥德尔编码(Gödel numbering)与ElGamal公钥加密算法,本文进一步提出了一种高效的云集合计算方案,该方案只需要n个参与者进行n次加密与一次解密,加密和解密的次数与参与者拥有集合元素的个数无关,具有较高的效率.为了方便说明,本文给出的集合隐私计算方案是在保密计算集合并集的基础上给出的,这些方案经过简单改造,也可以用来保密计算集合的交集.本文设计的解决方案均可以抵抗合谋攻击且具有广泛的适用范围,对于任何已知全集的集合计算方案都适用.

本文贡献如下:

(1) 为高效地解决保密的集合并集计算问题,设计了新的编码方法——1-r(0-r)编码方法.通过该编码方法将参与者拥有的集合编码成一个向量,避免了两两计算集合并集的习惯思维和两两计算可能导致的信息泄露;

(2) 为了抵抗合谋攻击,利用模运算的性质提出了密文分割方案,该方案可以把密文随机地分割成任意个份额,而且这些份额的乘积等于原来的密文.这种分割不需要对密文进行因子分解,具有较高的效率;

(3) 利用上述两种工具,提出了保密计算集合并集的协议,该协议具有很好的性质.可以用加法同态加密算法,也可以用乘法同态加密算法实现;可以借助半可信的云服务器实现保密计算集合的并集;经过简单改造,还可以保密计算集合的交集.这种方案的一个直接结果就是可以对多个集合中的数据进行保密排序.用模拟范例证明了协议的安全性;

(4) 利用哥德尔编码将一组数编码成一个数,对于一组数,只需要进行一次加密就可以进行集合并集的计算,进一步降低了协议的计算复杂性.

1 预备知识 1.1 隐私的集合计算问题

设n个参与者P₁,…,P_n分别拥有集合${X_1} = \{ {x_{11}},...,{x_{1{l_1}}}\} ,...,{X_n} = \{ {x_{n1}},...,{x_{n{l_n}}}\} \subset U$(其中,U={u₁,…,u_m}且u₁＜…＜u_m),组成二元组集合{(P₁,X₁),…,(P_n,X_n)}.他们想要在不泄露{(P₁,X₁),…,(P_n,X_n)}的前提下,计算这n个集合的交集或并集.

隐私计算集合的并集是指n个参与者计算这n个集合的并集X₁∪…∪X_n={σ₁,…,σ_h}(1≤h≤m),每个参与者可以知道所有集合的并集,而对其他参与者集合中的元素没有任何信息.

n个参与者计算这n个集合的交集X₁∩…∩X_n={σ₁,…,σ_h}(1≤h≤m),每个参与者可以知道所有集合的交集,而对其他参与者集合中的元素没有任何信息,这就是隐私计算集合的交集问题.

1.2 理想模型(ideal model)

假设有一个可信的第三方(trusted third party,简称TTP),他在任何情况下都不会撒谎,也绝不会泄露任何不该泄露的信息.理想的多方保密计算是指多个参与者借助可信的第三方进行保密计算.理想的多方保密计算模型可以描述为:有n个参与者P₁,…,P_n,他们分别将各自的秘密X₁,…,X_n告诉可信的第三方,由可信的第三方单独计算函数f:

$f\left( {{X_1}, \ldots {X_n}} \right) = \left( {{f_1}\left( {{X_1}, \ldots {X_n}} \right), \ldots {f_n}\left( {{X_1}, \ldots {X_n}} \right)} \right).$

然后,将计算结果f₁(X₁,…,X_n),…,f_n(X₁,…,X_n)分别告诉P₁,…,P_n.在计算过程中,P₁,…,P_n除了从协议得到可信第三方发送给自己的计算结果外得不到其他任何信息.理想的多方保密计算模型虽然简单,但具有最高的安全性,任何一个计算f(X₁,…,X_n)的实际多方保密计算协议的安全性都不可能超过这个协议,其他保密计算协议可以通过与理想模型进行比较来检验其安全性.理想多方保密计算方案存在的问题是:在遍布世界的网络环境中,要找到一个可信的第三方是极不现实的.

1.3 半诚实模型的安全性

本文假设所有的参与者都是半诚实参与者.半诚实参与者在协议的执行过程中会按照协议要求忠实地履行协议,执行协议后,除了协议的执行结果外没有任何信息泄露.但他们可能会记录下协议执行过程中收集到的所有信息,并试图根据收集到的信息(多个参与者时,我们应该考虑多个参与者在协议执行过程中收集到的信息,而不是一个参与者收集到的信息^[4])推算出其他参与者的输入.所以,半诚实模型又称为诚实但好奇模型或被动模型.

密码学不同领域中采用的安全性证明方法不同.基于可证明安全理论的证明适用于密码学中的加密与数字签名领域,而模拟范例是目前多方保密计算研究中广泛接受、普遍采用的证明方法.该方法的原理是将一个实际的多方保密计算协议与一个理想的多方保密计算协议的安全性进行对比,如果实际的多方保密计算协议不比理想的多方保密计算协议泄露更多信息,则实际的多方保密计算协议是安全的.

由于多数多方保密计算协议都是利用公钥加密算法构造的,因此多方保密计算协议的安全性证明一般是在假设相关公钥加密算法安全的条件下,具体的多方保密计算协议与理想的多方保密计算协议相比不会泄露更多的信息,即,将多方保密计算协议的安全性归约到公钥加密算法的安全性.假设公钥加密算法是安全的,那么一个参与者利用理想的多方保密计算协议得到的信息可以通过构造一个模拟器来模拟实际多方保密计算协议的执行过程.如果模拟的过程与实际执行过程是计算不可区分的,则说明实际协议是安全的.本文采用模拟范例对协议进行安全性证明.

假设n个参与者P₁,…,P_n分别拥有集合X₁,…,X_n,他们想要借助协议p保密地计算f(X₁,…,X_n).

令$\bar X = ({X_1},...,{X_n})$.在协议执行过程中,P_i(i=1,…,n)得到的信息序列记为$view_i^\pi (\bar X) = ({X_i},{r_i},M_i^1,...,M_i^t)$,其中,$M_i^j(j = 1,...,t)$表示P_i第j次得到的信息.对于I={i₁,…,i_s}⊆{1,…,n},我们令:

$view_I^\pi (\bar X) = (view_{{i_1}}^\pi (\bar X),...,view_{{i_s}}^\pi (\bar X))$

定义 1. 在参与者都是半诚实的情况下,如果存在概率多项式时间算法S对于每个I⊆{1,…,n}都使得式(1)成立,则协议p保密地计算n元函数f.

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}$

(1)

其中,${X_I} = ({X_{{i_1}}},...,{X_{{i_s}}}),\mathop \equiv \limits^c $表示计算上不可区分.

1.4 哥德尔编码

哥德尔在证明哥德尔不完备定理时,首创了哥德尔编码.哥德尔编码将非负整数序列与自然数建立起一一对应关系.有穷序列(a₁,…,a_m)借助素数序列(p₁,…,p_m)(其中,p₁,…,p_m可以是任意不同的m个素数,为了使计算简单,一般取从2开始的m个连续素数)建立如下的对应关系:

$[{a_1},...,{a_m}] = \prod\limits_{j = 1}^m {p_j^{{a_j}}} $

(2)

[a₁,…,a_m]称作有穷序列(a₁,…,a_m)的哥德尔数.根据算术基本定理,任意的自然数可以唯一地分解成多个素数的乘积,而构成哥德尔数的素数序列(p₁,…,p_m)是已知的,因此,由[a₁,…,a_m]可以很容易得到序列(a₁,…,a_m).

在本文中,我们用哥德尔编码建立起向量和自然数之间的一一对应关系.向量编码成的哥德尔数是一个非常大的数,这在日常的计算中将极大地增加计算量,但在密码学中,这样的增加是完全可以接受的.因为公钥密码学的计算都是在一个非常大的群中进行的,为了取得安全性,即使非常小的自然数加密也需要在一个很大的群中进行运算,这是依靠公钥加密保证安全必须付出的代价.

1.5 同态加密算法

一个传统的公钥加密方案e包括3种算法:KeyGen_ε,Encrypt_ε,Decrypt_ε.对于KeyGen_ε算法,给定一个安全参数λ,输出一个私钥sk和对应的公钥pk,并给定明文空间P和密文空间C,即:

· KeyGen_ε(λ)←(sk,pk,P,C);

· Encrypt_ε算法对于给定的公钥pk和明文M∈P输出相应的密文C∈C,即:

${\rm{Encryp}}{{\rm{t}}_\varepsilon }\left( {pk,M} \right) \leftarrow \left( C \right)\left( {M \in p} \right).$

· 根据密文C和私钥sk,Decrypt_ε算法输出相应的明文M:

${\rm{Decryp}}{{\rm{t}}_\varepsilon }\left( {sk,C} \right) \leftarrow \left( M \right)\left( {C \in C} \right).$

一个同态加密算法e除了以上3种算法外,还包括一个多项式时间的Evaluate_ε算法.如果C_i是M_i用公钥pk加密的密文,为算法Evaluate_ε输入公钥pk、一种操作S和密文组$C\langle {C_1}, \ldots ,{C_m}\rangle $,算法Evaluate_ε输出S(M₁,…,M_m)的密文,即:

${\rm{Evaluat}}{{\rm{e}}_\varepsilon }\left( {pk,S,C} \right) \leftarrow {\rm{Evaluat}}{{\rm{e}}_\varepsilon }\left( {pk,S\left( {{M_1}, \ldots {M_m}} \right)} \right).$

ElGamal公钥加密算法是具有乘法同态性质的加密算法.对于消息M,其密文可以表示成如下形式:

$E\left( M \right) = \left( {{c_1},{c_2}} \right) = \left( {{g^r}\bmod p,M{H^r}\bmod p} \right).$

其中,r是加密者选择的一个随机数,h=g^x mod p是私钥x对应的公钥.

对消息M₁,M₂的密文做乘法运算:

$C\langle {C_1}, \ldots ,{C_m}\rangle $

即:对M₁,M₂的密文做乘法运算,相当于对M₁,M₂做乘法运算之后再加密.如果M₁=1,对M₁的密文与M₂的密文做Evaluate运算后,得到M₂不同的密文.

Paillier公钥加密算法^[27]是一种具有加法同态性质的加密算法.消息M的密文可以表示为

$E\left( M \right) = {g^M}{r^N}\bmod {N^2}.$

其中,M∈Z_N,N是RSA算法中的模数;$r \in Z_N^*$是加密者选择的随机数.对消息M₁,M₂的密文做乘法运算:

$E({M_1}) \times E({M_2}) = ({g^{{M_1}}}r_1^N\bmod {N^2}) \times ({g^{{M_2}}}r_2^N\bmod {N^2}) = {g^{{M_1} + {M_2}}}{({r_1} \cdot {r_2})^N}\bmod {N^2} = E({M_1} + {M_2})$

因此,对消息M₁,M₂的密文做乘法运算,相当于对其明文做加法运算之后再加密.与ElGamal公钥加密算法类似,如果M₁=0,对M₁的密文与M₂的密文运算得到M₂新的密文.

2 保密计算集合并集的解决方案

保密计算集合并集是隐私保护、保密的数据挖掘、保密的图算法等许多协议的基本模块,具有重要的现实意义与理论价值.例如在隐私保护的分布式网络监控中,有n个监控点P₁,…,P_n,每个监控点P_i(i=1,…,n)记录下的不良网络行为记为集合X_i,为了更好地维护网络的安全,这n个监控点想要知道在这个网络中都有哪些不良的网络行为,以便更快地检测到不良行为,降低网络的风险.但是为了隐私不能泄露每个结点检测到的具体的不良行为,这需要n个监控结点保密地计算这n个结点检测到的不良行为的并集.

2.1 基本原理

1-r 编码方法. 集合X_i⊂U={u₁,…,u_m}(其中,u₁＜…＜u_m)编码为1-r向量U_i=(u_i1,…,u_im)的方法如下:

 For j=1 to m

  If u_j∈X_i

   u_ij←r_ij

  Else u_ij←1

 End

假设有n个集合X₁,…,X_n⊂U={u₁,…,u_m}(其中,u₁＜…＜u_m),将每个集合X_i(i=1,…,n)借助于1-r编码方法编码成向量U_i=(u_i1,…,u_im),然后将各个向量的对应分量相乘得到新的向量U´.

$U' = {U_1}...{U_n} = ({u_{11}}...{u_{n1}},...,{u_{1m}}...{u_{nm}}) = ({u'_1},...,{u'_m}).$

如果向量U´中的某个分量${u'_j} \ne 1$,则说明这n个向量的第j个分量不全为1,即,n个集合中至少有一个集合含有元素u_j.根据向量U´中不为1的分量,可以得到X₁∪…∪X_n={σ₁,…,σ_h}(1≤h≤m).因此,保密计算集合并集问题可以归约到保密地计算向量U´.

以下是利用1-r编码方法计算集合并集的实例(实例1).为了简单说明,实例1中给出的是计算3个集合X₁,X₂,X₃⊂U的并集.

2.2 具体方案

在云计算环境中,云服务器之间是不完全可信的,不能直接将明文数据在云服务器之间传递.因此,需要云服务器借助加密算法将私有的数据先进行加密,然后再将加密数据在云服务器之间传递,让云服务器对密文做处理来实现数据的隐私保护.

云服务器P_n输入选定的安全参数λ,运行ElGamal公钥加密算法的KeyGen算法,输出相应的系统参数params=(p,g)、私钥sk=(x)和对应的公钥pk=(h).其中,

· p是由安全参数l决定的大素数,此外,为了确保ElGamal公钥加密算法在乘法群Z_p^*上计算离散对数是困难的,需要φ(p)=p-1中至少含有一个大的素因子;

· g是Z_p^*的一个生成元;

· 公钥h是由私钥生成的,即h=g^x mod p.

P_n保存私钥sk并将公钥pk与系统参数params公布,供其他云服务器使用.

每个云服务器P_i(i=1,…,n)将其秘密集合X_i(X_i⊂U={u₁,…,u_m},其中,u₁＜…＜u_m)根据1-r编码方法编码成向量U_i=(u_i1,…,u_im).P_i用P_n公布的公钥pk与系统参数params将自己构造的向量U_i加密,即,将向量U_i中的每个分量分别加密.

$E\left( {{U_i}} \right) = \left( {E\left( {{u_{i1}}} \right), \ldots E\left( {{u_{im}}} \right)} \right).$

如果直接将E(U_i)发送给P_n,P_n可以将密文解密,从而知道其他云服务器的秘密集合,即使P_n是完全可信的,但由于所有的服务器都将加密的向量发送给P_n,P_n将成为敌手攻击的众矢之的,因此需要借助于其他的方法防止P_n解密得到其他云服务器的信息.本文根据同态加密算法的性质,采用将P_i拥有的明文与P_i发送给P_n的密文混淆的方法来保证U_i的安全.P_i将E(u_ij)(j=1,…,m)分成非零的k_i(k_i≤n)份(其中,k_i可以是不确定的,其他云服务器得不到任何有关k_i的信息),即$E{({u_{ij}})_1},...,E{({u_{ij}})_{{k_i}}}$.由于ElGamal公钥加密算法是具有乘法同态性的,为了保证正常解密,需要使:

$E{({u_{ij}})_1}...E{({u_{ij}})_{{k_i}}} = E({u_{ij}})$

P_i每次从每个密文分量中取出一份不同的份额,共取k_i次,构成U_i的k_i份密文$E{({U_i})_1},...,E{({U_i})_{{k_i}}}$,然后将这k_i份密文发送给n个云服务器中的k_i个.这k_i个云服务器可以包括P_i自己,也可以不包括,其他云服务器得不到这k_i个云服务器的任何信息.

在ElGamal公钥加密算法中,由于密文属于一个非常大的群Z_p^*,将密文如E(u_ij)(1≤i≤n,1≤j≤m)分成k_i份是困难的,Z_p^*中也包括一些不能进行因子分解的整数,或一些因子少于k_i个的整数,因此,我们不能直接利用因子分解的方法将密文分成k_i份.

在本方案中,由于云服务器在做Evaluate运算时只需要保证等式$E{({u_{ij}})_1}...E{({u_{ij}})_{{k_i}}} = E({u_{ij}})$成立,因此不需要真的将密文按照因子分解的方法分成k_i份,根据模运算的性质,只需要选择k_i个随机数${r_{i1}},...,{r_{i{k_i}}} \in Z_p^*$,同时保证这些随机数满足${r_{i1}}...{r_{i{k_i}}} = 1{\rm{ }}\bmod {\rm{ }}p$.从这k_i个随机数中随机地选择一个随机数如r_i1,将其与E(u_ij)相乘构成E(u_ij)的一份份额如E(u_ij)₁=E(u_ij)⋅r_i1,然后将$E{({u_{ij}})_2},...,E{({u_{ij}})_{{k_i}}}$分别用${r_{i2}},...,{r_{i{k_i}}}$表示,则:

$E{({u_{ij}})_1}...E{({u_{ij}})_{{k_i}}} = {r_{i1}} \cdot E({u_{ij}}) \cdot {r_{i2}}...{r_{i{k_i}}} = E({u_{ij}})$

该密文拆分方法只需要将消息加密1次,具有较高的效率.

在本方案中,云服务器P_i(i=1,…,n)将其密文向量E(U_i)分成k_i份并发送给n个云服务器中的k_i个,其他任何一个云服务器得不到全部k_i份密文,即使拥有私钥sk也得不到关于U_i的任何信息.不妨设敌手得到关于E(U_i)的k_i-1份密文$E{({U_i})_1},...,E{({U_i})_{{k_i} - 1}}$,因为:

$E{({U_i})_1}...E{({U_i})_{{k_i} - 1}} \cdot E{({U_i})_{{k_i}}} = E({U_i})$

在这个方程中,敌手不知道$E{({U_i})_{{k_i}}}$与E(U_i),敌手得到的是不定方程,即使敌手拥有私钥sk,可以将$E{({U_i})_1},...,E{({U_i})_{{k_i} - 1}}$解密,也得不到关于U_i的任何信息.因此,每个云服务器将其密文分成k_i份发送给n个云服务器中的k_i个是安全的.

每个云服务器P_i(i=1,…,n)将密文分发后,也会收到其他云服务器发送过来的密文向量.P_i将收到的密文向量的每个相应分量分别相乘,构成新的密文向量$E({U'_i}) = (E({u'_{i1}}),...,E({u'_{im}}))$并发送给云服务器P_n,从而实现云服务器发送的密文与自身明文关系的混淆.

云服务器P_n将收到所有密文向量的对应分量分别相乘,得到E(U´),即:

$E(U') = E({U'_1})...E({U'_n}) = (E({u'_{11}})...E({u'_{n1}}),...,E({u'_{1m}})...E({u'_{nm}}))$

由于每个云服务器都是半诚实参与者,在协议的执行过程中会严格按照协议的要求执行协议,且不会加入其他信息,所以P₁构造的密文向量E(U´)是所有参与者密文向量各个分量的乘积,即:

$E(U') = E({U_1})...E({U_n}) = (E({u_{11}})...E({u_{n1}}),...,E({u_{1m}})...E({u_{nm}})) = (E({u'_1}),...,E({u'_m}))$

P_n用自己的私钥将$E(U') = (E({u'_1}),...,E({u'_m}))$解密,得到向量$U' = ({u'_1},...,{u'_m})$.P_n根据U´中不为1的元素与集合U的关系,得到X₁∪…∪X_n={σ₁,…,σ_h}(1≤h≤m)并将其公布.从而,每个云服务器得到了n个云服务器拥有集合的并集.在此基础上给出了保密计算集合并集的解决方案,具体协议如下:

协议 1. n个云服务器保密计算集合的并集.

输入:P₁,…,P_n各自的秘密集合X₁,…,X_n⊂U={u₁,…,u_m};

输出:X₁∪…∪X_n={σ₁,…,σ_h}(1≤h≤m).

1. 云服务器P_n将自己的公钥pk与系统参数params公布,并保留私钥sk;

2. 每个云服务器P_i(i=1,…,n)计算如下:

(1) 将自己的秘密集合X_i编码为向量U_i;

(2) 用P_n的公钥pk与系统参数params加密U_i为E(U_i);

(3) 将密文向量E(U_i)随机地分成k_i份并发送给n个云服务器中的k_i个;

(4) 把收到的所有密文向量对应的分量相乘得到新的密文向量$E({U'_i})$,并发送给P_n;

3. 云服务器P_n计算如下:

(1) 所有收到的密文向量对应的分量相乘,得到E(U´);

(2) 用自己的私钥sk解密E(U´)得到U´;

(3) 根据U´中不为1的分量得到{σ₁,…,σ_h};

(4) 公布{σ₁,…,σ_h}.

为了便于理解,我们设计了一个包含4个云服务器的保密计算集合并集的实例.云服务器P₁,…,P₄(仅P₄拥有私钥sk)分别拥有秘密集合X₁,…,X₄⊂U={u₁,…,u_m},他们根据1-r编码方法分别将X₁,…,X₄编码为向量U₁,…,U₄,进而根据P₄公布的公钥pk将编码的向量加密为E(U₁),…,E(U₄).P_i(i=1,…,4)密文分成的份数和密文份额发送给的云服务器都是不确定的,本例为了说明简单,假设P_i将其密文向量分成3份,自己保留1份,另外两份分别发送给云服务器P_{i+1(mod 4)},P_{i+2(mod 4)}(如图 1的实线表示).在密文向量分发后,P_i将收到的密文向量的乘积$E({U'_i})$发送给P₄(如图中虚线表示).P₄得到:

$\eqalign{ & E(U') = E({{U'}_1})...E({{U'}_4}) \cr & {\rm{ }} = E{({U_1})_3}E{({U_3})_2}E{({U_4})_1} \cdot E{({U_2})_3}E{({U_1})_1}E{({U_4})_2} \cdot E{({U_3})_3}E{({U_2})_1}E{({U_1})_2} \cdot E{({U_4})_3}E{({U_3})_1}E{({U_2})_2} \cr & {\kern 1pt} {\rm{ }} = E({U_1}) \cdot E({U_2}) \cdot E({U_3}) \cdot E({U_4}). \cr} $

P₄将E(U´)解密,得到U´,根据U´中不为1的元素得到X₁∪…∪X_n={σ₁,…,σ_h},然后将{s₁,…, s_h}公布,这4个云服务器得到了它们集合的并集.

协议1 描述的是有n个云服务器P₁,…,P_n分别拥有秘密集合X₁,…,X_n,他们想要知道这n个集合的并集而不泄露各自秘密集合的信息.该方案也可以看作是每个用户均拥有一个可信云服务器的情况.根据1-r编码方法,对用户借助半可信云服务器保密计算集合并集的情况,该方案经过简单改造也同样适用.

在协议1中,每个云服务器P_i(i=1,…,n)需要将秘密集合X_i(X_i⊂U={u₁,…,u_m},其中,u₁＜…＜u_m)根据1-r编码方法编码成向量U_i=(u_i1,…,u_im),然后将向量U_i加密,在云服务器之间对密文进行计算来实现集合并集的保密计算.由于P_i将向量U_i加密,仅相当于加密1和随机数r≠1,加密1和r是公开的,只需要保密1和r所在的位置,因此可以将加密运算外包给半可信的云服务器S.

将云服务器P₁,…,P_n看作云用户P₁,…,P_n,他们想要借助半可信云服务器S保密地计算集合X₁,…,X_n⊂U={u₁,…,u_m}的并集.由于ElGamal加密算法是概率加密算法,同一个明文可以有多个不同的密文,每个云用户P_i(i=1,…,n)让云服务器S加密一些1,生成一些随机数r供自己构造向量U_i的密文.对于向量U_i的每个分量u_ij(j=1,…,m),当u_ij=1时,P_i从E(1)中随机地选择k_i个E(1),作为E(u_ij)的k_i(k_i≤n)个份额;当u_ij=r_ij时,P_i从E(1)中随机地选择k_i-1个E(1),再随机地选择$r \in Z_p^*$作为E(r),因为随机数的密文仍是一个随机数,将k_i-1个E(1)和E(r)作为E(u_ij)的k_i(k_i≤n)个份额.P_i每次从各个密文分量中取出一份不同的份额,共取k_i次,构成U_i的k_i份密文$E{({U_i})_1},...,E{({U_i})_{{k_i}}}$,然后将这k_i份密文发送给n个云用户中的k_i个.P_i把收到的所有密文向量对应的分量相乘得到新的密文向量$E({U'_i})$,并发送给云服务器S.S将所有收到的密文向量对应的分量分别相乘,得到密文向量E(U´),把E(U´)发送给P_n.P_n用自己的私钥sk解密E(U´)得到U´,根据U´中不为1的元素得到X₁∪…∪X_n={s₁,…,s_h}并公布.

在改造过的方案中,虽然半可信云服务器S为每个云用户服务,但是在整个过程中,S得到的关于用户P_i的信息只有一些E(1)、随机数r与$E({U'_i})$,并不影响协议的安全性.此外,经过改造,仅需要每个云用户做少量的模乘运算,P_n做m次解密,加密运算全部由S完成,参与者P₁,…,P_n的计算量大大降低,真正地借助于云实现了保密计算集合的并集.

以上方案也可以用加法同态加密算法(Paillier加密算法)来构造,只需要将E(1)用E(0)替代.在编码时,每个云服务器将其集合编码成0-r的向量,不属于其集合中元素的位置用0替代,为属于集合中的元素选择一个不为0的随机数.最后,P_n根据U´中不为0的元素与集合U的关系得到X₁∪… ∪X_n={σ₁,…,σ_h}.由于现有的乘法同态加密算法比加法同态加密算法效率高,因此本文采用的是具有乘法同态性质的ElGamal公钥加密算法.根据方案中的计算方法可知,得到的并集{σ₁,…,σ_h}中的元素是严格递增的,即,σ₁＜…＜σ_h.因此,该协议还可以实现保密地计算多个云服务器集合的交集.

2.3 方案分析

模拟范例是在半诚实模型下研究多方保密计算时广泛接受、普遍采用的证明方法,由于半诚实模型下的云多方保密计算属于半诚实模型下的多方保密计算,因此可以采用模拟范例的方法证明.关于协议1的安全性,有以下定理1:

定理 1. n个云服务器保密计算集合的并集协议1(记为∏)是保密的.

证明:根据协议1中参与合谋的云服务器的不同,分为以下3种情况证明∏的安全性.

(1) 云服务器P_n不参与合谋,其他云服务器集合P_I⊆{P₁,…,P_n-1}合谋想要得到云服务器P_i(P_i∉P_I,i=1,…,n)集合X_i中的元素,令X_I=(X₁,…,X_i-1,X_i+1,…,X_n-1).通过构造使下式成立的概率多项式时间模拟器S来证明上述情况的安全性:

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\Pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}$

S的模拟过程如下:

① 给定输入$({X_I},{f_I}(\bar X))$,令$({X_I},{f_I}(\bar X)) = ({X_1},...,{X_{i - 1}},{X_{i + 1}},...,{X_{n - 1}},{f_I}(\bar X))$,S随机选择两个集合${X'_n},{X'_i}$,使得${f_I}(\bar X) = {f_I}(\bar X')$,其中,$\bar X' = ({X_1},...,{X_{i - 1}},{X'_i},{X_{i + 1}},...,{X_{n - 1}},{X'_n})$.

② S首先按照∏中1-r编码方法将$\bar X'$中的每个集合编码成向量${U_1},...,{U_{i - 1}},U_i^*,{U_{i + 1}},...,{U_{n - 1}},U_n^*$;然后,用P_n公布的(pk,params)将向量${U_1},...,{U_{i - 1}},U_i^*,{U_{i + 1}},...,{U_{n - 1}},U_n^*$中的每个分量分别加密,得到密文向量:

$E({U_1}),...,E({U_{i - 1}}),E(U_i^*),E({U_{i + 1}}),...,E({U_{n - 1}}),E(U_n^*);$

随后,将n个密文向量分别随机地分成k₁,…,k_n份,模拟P中的分发方法进行分发.

③ S将各个密文向量随机地分发,对收到的密文做Evaluate运算,构成新的密文向量:

$E(U_1^*),...,E(U_{i - 1}^*),E(U_i^ \circ ),E(U_{i + 1}^*),...,E(U_{n - 1}^*),E(U_n^ \circ ).$

④ S对所有密文向量对应的分量做Evaluate运算,得到:

$E(U') = E(U_1^*)...E(U_{i - 1}^*) \cdot E(U_i^ \circ ) \cdot E(U_{i + 1}^*)...E(U_{n - 1}^*) \cdot E(U_n^ \circ ).$

⑤ 由于P_n∉P_I,ElGamal公钥加密算法的安全性是基于DDH困难性假设的,DDH困难性假设认为,概率多项式时间算法的敌手不能区分元组D=(g^a,g^b,g^ab)与$R = ({g^a},{g^b},{g^c})(a,b,c \in Z_p^*)$,即,不能对密文解密.S是具有概率多项式时间计算能力的模拟器,且没有ElGamal公钥加密算法的私钥,不能对密文进行解密,只能根据协议执行结束时得到的{σ₁,…,σ_h}推算出U´,进而计算出$\{ {\sigma '_1},...,{\sigma '_h}\} .$

在∏中:

$\eqalign{ & view_I^\Pi (\bar X) = \{ view_1^\Pi (\bar X),...,view_{i - 1}^\Pi (\bar X),view_{i + 1}^\Pi (\bar X),...,view_{n - 1}^\Pi (\bar X)\} \cr & {\kern 1pt} {\rm{ }}{\kern 1pt} = \{ ({X_1},...,{X_{i - 1}},{X_{i + 1}},...,{X_{n - 1}}),({U_1},...,{U_{i - 1}},{U_{i + 1}},...,{U_{n - 1}}), \cr & {\kern 1pt} {\rm{ }}(E({U_1}),...,E({U_{i - 1}}),E({U_{i + 1}}),...,E({U_{n - 1}})), \cr & {\rm{ }}(E({{U'}_1}),...,{\kern 1pt} E({{U'}_{i - 1}}),E({{U'}_{i + 1}}),...,E({{U'}_{n - 1}})),E(U'),({\sigma _1},...,{\sigma _h})\} , \cr} $

令:

$\eqalign{ & S({X_I},{f_I}(\bar X)) = \{ ({X_I},...,{X_{i - 1}},{X_{i + 1}},...,{X_{n - 1}}),({U_1},...,{U_{i - 1}},{U_{i + 1}},...,{U_{n - 1}}), \cr & {\rm{ }}(E({U_1}),...,E({U_{i - 1}}),E({U_{i + 1}}),...,E({U_{n - 1}})), \cr & {\rm{ }}(E(U_1^*),...,E(U_{i - 1}^*),E(U_{i + 1}^*),...,E(U_{n - 1}^*)),E({U^*}),({{\sigma '}_1},...,{{\sigma '}_h})\} , \cr} $

因为$({\sigma _1},...,{\sigma _h}) = ({\sigma '_1},...,{\sigma '_h})$,由于ElGamal公钥加密算法是语义安全的,用语义安全加密算法加密的数据是计算不可区分的,上述模拟过程中得到的消息序列与实际执行过程中得到的消息序列是计算不可区分的,即:

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\Pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}.$

所以,∏在该情况下是保密的.

(2) 云服务器P_n与其他云服务器集合P_I´⊆{P₁,…,P_n-1}合谋想要得到云服务器P_i∉P_I(I=I´∪n,i=1,…,n)集合X_i中的元素.P_i将其机密集合X_i编码成向量U_i并加密为E(U_i),然后将E(U_i)随机地分成k_i份发送给n个云服务器中的k_i个,其他云服务器对于P_i将这k_i份密文发送给了哪k_i个云服务器没有任何信息.云服务器集合P_I不知道收到的关于E(U_i)的份额是否是全部份额,因此,即使P_n与P_I´将收到的关于E(U_i)的全部份额相应分量相乘并解密,根据解密后得到的明文也不能确定向量U_i,即,不能得到关于集合X_i中的元素.在协议执行后,除P_i外的其他全部云服务器合谋可能会得到关于X_i的信息,因为P_n与P_I根据{σ₁,…,σ_h}和集合X₁,…,X_i-1,X_i+1,…,X_n的关系,得到一些关于U_i的信息,但是由于所有集合中的相同元素在集合{σ₁,…,σ_h}中仅出现一次,因此其他云服务器只会得到集合X_i独有的元素,这与借助于可信的第三方的理想模型的执行结果是一样的,不会泄漏更多的信息.所以,该情况下存在概率多项式时间算法S(S根据情形(1)容易构造,在此省略其构造过程)对于I使得下式成立:

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\Pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}.$

(3) 云服务器P_n与其他云服务器集合P_I´⊆{P₁,…,P_n-1}合谋,想要得到云服务器集合${P_{\bar I}} = \{ {P_1},...,{P_{n - 1}}\} - {P_I}$(I= I´∪n)中云服务器的元素.当${P_{\bar I}}$中只有一个元素时,不妨令除P_i外的其他云服务器合谋想要得到集合X_i中的元素,这与情形(2)中的情况类似,和借助于理想模型的结果一样.当${P_{\bar I}}$中有两个元素时,不妨令除P_i,P_i+1外的云服务器合谋想要得到集合X_i,X_i+1中的元素,他们最终只能得到关于向量U_i,U_i+1的一个不定方程:

$U' = {U_1} \ldots {U_i} \cdot {U_{i + 1}} \ldots {U_n}.$

因此得不到向量U_i,U_i+1各个分量的值,即,不能得到关于P_i,P_i+1集合X_i,X_i+1中的元素.当${P_{\bar I}}$中的元素多于两个时,情况与有两个元素类似.因此,云服务器集合P_I合谋得不到${P_{\bar I}}$中云服务器的元素.所以,该情况下也存在概率多项式时间算法S(根据情形(1)容易构造S,在此省略具体的构造过程)对于I使得下式成立:

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\Pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}.$

3 保密计算集合并集问题的高效解决方案

上述方案的计算复杂性与集合U中元素的个数m线性相关,如果m较大,加密、解密的次数与通信量将会比较大,不便于计算.如果m不太大,在协议1的基础上,根据哥德尔编码将向量对应成一个唯一自然数的方法设计了一种高效的编码方法,使协议的计算复杂性不再与集合U中元素的个数m相关,降低了计算的复杂性.

3.1 高效编码方法基本原理

将集合U={u₁,…,u_m}(其中,u₁＜…＜u_m)对应成集合P={p₁,…,p_m},其中,u_j(j=1,…,m)对应于p_j(j=1,…,m),p₁,…,p_m是m个互不相等的素数.为了便于计算,取从2开始的m个连续素数.对于集合X_i⊂U,将其按照0-r编码的方法编码成0-r向量U_i=(u_i1,…,u_im).如果u_j∈X_i(j=1,…,m),则u_ij=r_ij,其中,r_ij∈[1,m]是一个随机数且r_ij≠0(r_ij≠0是为了将集合X_i中的元素与集合${\bar X_i} = U - {X_i}$中的元素区分,但为了防止根据r_1j+…+r_nj推算出拥有元素u_j集合的数目,r_ij必须是一个随机数;如果${r_{ij}} \in Z_p^*$,将很可能因为编码成的数过大而得不到正确的计算结果,因此令r_ij取自较小的范围[1,m]);否则,u_ij=0.然后,将向量U_i借助集合P利用哥德尔编码的方法编码成一个自然数x_i,即:

$[{u_{i1}},...,{u_{im}}] = p_1^{{u_{i1}}}...p_m^{{u_{im}}} = {x_i}.$

假设有n个集合X₁,…,X_n⊂U,将每个集合X_i(i=1,…,n)都按照高效编码方法编码成一个自然数x_i,将这n个自然数相乘得到x,即:

$x = {x_1}...{x_n} = p_1^{{u_{11}}}...p_m^{{u_{1m}}}...p_1^{{u_{n1}}}...p_m^{{u_{nm}}} = p_1^{{u_{11}} + ... + {u_{n1}}}...p_m^{{u_{1m}} + ... + {u_{nm}}} = p_1^{{{u'}_1}}...p_m^{{{u'}_m}}$

根据算术基本定理将x展开,得到集合$U' = \{ {u'_1},...,{u'_m}\} $.如果${u'_j} = {u_{1j}} + ... + {u_{nj}} \ne 0(j = 1,...,m)$,则u_1j,…,u_nj中至少有一个不为0,说明n个集合中至少有一个集合含有u_j.根据向量U´中不为0的分量,可以得到X₁∪…∪X_n= {σ₁,…,σ_h}(1≤h≤m).因此,保密计算集合并集的问题可以归约到保密地计算x.以下是借助于高效编码方法计算集合并集的具体实例.

实例 2. 为了便于理解,仍以实例1中的数据为例进行说明.集合U={101,102,103,104,105,106,107,108,109,110}对应于集合P={2,3,5,7,11,13,17,19,23,31},假设要计算3个集合X₁={101,105,107},X₂={103,105,108},X₃= {104,106,109}⊂U的并集,根据0-r编码方法将集合X₁,X₂,X₃分别编码成0-r向量U₁,U₂,U₃,即:

$\eqalign{ & {U_1} = (3,0,0,0,2,0,1,0,0,0), \cr & {U_2} = (0,0,2,0,1,0,0,2,0,0), \cr & {U_3} = (0,0,0,2,0,1,0,0,1,0). \cr} $

将向量U₁,U₂,U₃借助于集合P利用哥德尔编码的方法编码成自然数x₁,x₂,x₃,即:

$\eqalign{ & {x_1} = [3,0,0,0,2,0,1,0,0,0] = {2^3} \cdot {11^2} \cdot {17^1} = 16456, \cr & {x_2} = [0,0,2,0,1,0,0,2,0,0] = {5^2} \cdot {11^1} \cdot {19^2} = 99275, \cr & {x_3} = [0,0,0,2,0,1,0,0,1,0] = {7^2} \cdot {13^1} \cdot {23^1} = 14651. \cr} $

将这3个自然数相乘得到:

$x = {x_1} \cdot {x_2} \cdot {x_3} = 23934890379400 = {2^3} \cdot {3^0} \cdot {5^2} \cdot {7^2} \cdot {11^3} \cdot 13 \cdot 17 \cdot {19^2} \cdot {23^1} \cdot {29^0}.$

即得到向量U´=(3,0,2,2,3,1,1,2,1,0).根据向量U´中不为0的分量得到:

${X_1} \cup {X_2} \cup {X_3} = \left\{ {101,103,104,105,106,107,108,109} \right\}.$

3.2 具体方案

云服务器P_n给ElGamal公钥加密算法的KeyGen算法输入安全参数l,输出相应的系统参数params= (p,g),私钥sk=(x)与对应的公钥pk=h(h=g^x mod p).P_n将pk,params公布并保留sk.

每个云服务器P_i(i=1,…,n)将私有集合X_i借助高效编码方法编码成自然数x_i,把x_i用P_n公布的pk,params加密为E(x_i).如果直接将E(x_i)发送给P_n是不安全的,P_n可以通过解密将x_i恢复,因此需要借助其他方法混淆密文与云服务器的对应关系.P_i将E(x_i)随机地分成非零的k_i(k_i≤n)份(k_i的值是不确定的且其他云服务器没有任何信息)$E{({x_i})_1},...,E{({x_i})_{{k_i}}}$,为了保证ElGamal公钥加密算法正常解密,需要使$成立.将E(x_i)分成k_i份,只需要选择k_i个随机数${r_{i1}},...,{r_{i{k_i}}}$,它们满足${r_{i1}}...{r_{i{k_i}}} = 1{\rm{ }}\bmod {\rm{ }}p$,然后.从k_i个随机数中选择1个随机数如r_i1与E(x_i)相乘构成E(x_i)的一份份额如E(x_i)₁=r_i1⋅E(x_i),用${r_{i2}},...,{r_{i{k_i}}}$分别表示$E{({x_i})_2},...,E{({x_i})_{{k_i}}},$则:

$E{({x_i})_1}...E{({x_i})_{{k_i}}} = {r_{i1}} \cdot E({x_i}) \cdot {r_2}...{r_{i{k_i}}} = E({x_i}).$

P_i将${r_{i1}} \cdot E({x_i}),{r_{i2}},...,{r_{i{k_i}}}$分别发送给n个云服务器中的k_i个.这k_i个云服务器可以包括P_i自己也可以不包括,具体发给了哪k_i个云服务器,其他云服务器没有任何信息.假设敌手已经获得关于E(x_i)的k_i-1份份额,不妨令敌手得到的密文份额为$E{({x_i})_1},...,E{({x_i})_{{k_i} - 1}}$,因为$E{({x_i})_1}...E{({x_i})_{{k_i} - 1}} \cdot E{({x_i})_{{k_i}}} = E({x_i})$,敌手不知道方程中的$E({x_i}),E{({x_i})_{{k_i}}},$得到的是有两个未知数的不定方程,即使敌手拥有私钥sk可以解密$E{({x_i})_1},...,E{({x_i})_{{k_i} - 1}}$,也无法得到有关x_i的信息,因此,每个云服务器将密文分成k_i份发送给n个云服务器中的k_i个是安全的.P_i将密文分发后,也会收到其他云服务器发送过来的密文.P_i对收到的所有密文做Evaluate运算,构成新的密文$E({x'_i})$并发送给P_n.

云服务器P_n把收到的所有密文做Evaluate运算,得到E(x).由于协议中的每个云服务器都是半诚实参与者,在协议执行过程中会严格按照协议要求执行协议,不会加入其他信息,所以P_n构造的E(x)是所有云服务器秘密数的密文之积,即E(x)=E(x_i)…E(x_n).P_n用私钥sk把E(x)解密得到明文x,然后将x用算术基本定理展开,得到$x = p_1^{{{u'}_1}}...p_m^{{{u'}_m}}$,即,向量$U' = ({u'_1},...,{u'_m})$.P_n根据U´中不为0的分量与集合U的关系得到集合{σ₁,…,σ_h}⊂U(1≤h≤m),并将其公布.n个云服务器得到了保密计算集合并集的结果.在此基础上,给出了高效的保密计算集合并集协议,具体如协议2.

协议 2. 高效的保密计算集合并集.

输入:P₁,…,P_n各自的秘密集合X₁,…,X_n⊂U={u₁,…,u_m};

输出:X₁∪…∪X_n={σ₁,…,σ_h}(1≤h≤m).

1. 云服务器P_n保留私钥sk公布公钥pk与系统参数params;

2. 每个云服务器P_i(i=1,…,n)计算如下:

(1) 根据高效编码方法将自己的秘密集合X_i编码成自然数x_i;

(2) 用公钥pk加密x_i为E(x_i);

(3) 把E(x_i)随机地分成k_i份并发送给n个云服务器中的k_i个;

(4) 将收到的所有密文相乘得到新的密文$E({x'_i})$,并发送给P_n;

3. 云服务器P_n计算如下:

(1) 把所有收到的密文相乘,得到E(x);

(2) 用私钥sk解密E(x)得到x;

(3) 将x用算术基本定理展开得到向量U´;

(4) 根据U´中不为0的分量得到集合{σ₁,…,σ_h}并公布.

根据方案的计算方法可知:得到的并集{σ₁,…,σ_h}中的元素是严格递增的,即,σ₁＜…＜σ_h.因此,该协议还可以实现保密地计算多个云服务器集合中所有元素的排序.该协议与协议1经过简单的改造也适用于w个云用户借助n个半可信云服务器P₁,…,P_n保密计算集合并集的问题,现以协议2为例作简单说明.假如有w个云用户V₁,…,V_w,他们想要借助半可信的云保密计算集合的并集.每个云用户V_i用高效编码方法把自己的秘密集合转化成秘密数x_i,并将x_i随机地分成k_i份发送给n个云服务器中的k_i个.这n个云服务器将收到的秘密份额相乘并加密,然后将密文发送给P_n.P_n将所有的密文相乘并解密,得到x,从而得w个云用户集合的并集{σ₁,…,σ_h}.虽然需要n个云服务器合作计算w个云用户的并集,但是计算出云用户的秘密集合需要得到相应秘密数的全部信息,而每个云服务器没有任何一个云用户秘密向量的全部信息,因此得不到云用户的信息,从而可以得到w个云用户的并集.

3.3 方案分析

我们采用模拟范例的方法证明了协议2的安全性,具体如定理2.

定理 2. 高效的保密计算集合并集协议2(记为p)是保密的.

证明:分3种情况证明π的安全性:

(1) 云服务器P_n不参与合谋,其他云服务器集合P_I⊆{P₁,…,P_n-1}合谋想要得到云服务器P_i(P_i∉P_I,i=1,…,n)集合X_i中的元素.通过构造使下式成立的概率多项式时间模拟器S来证明上述情况的安全性:

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}$

S的工作过程如下:

① 给定输入$({X_I},{f_I}(\bar X))$,令:

$({X_I},{f_I}(\bar X)) = ({X_I},...,{X_{i - 1}},{X_{i + 1}},...,{X_{n - 1}},{f_I}(\bar X)),$

S随机选择两个集合${X'_n},{X'_i}$,使得${f_I}(\bar X) = {f_I}(\bar X')$,其中,$\bar X' = ({X_1},...,{X_{i - 1}},{X'_i},{X_{i + 1}},...,{X_{n - 1}},{X'_n}).$

② S按照π中高效的编码方法将$\bar X'$中的每个集合编码成自然数${x_1},...,{x_{i - 1}},x_i^*,{x_{i + 1}},...,{x_{n - 1}},x_n^*$,然后用P_n公布的ElGamal公钥加密算法的公钥与系统参数(pk,params)将${x_1},...,{x_{i - 1}},x_i^*,{x_{i + 1}},...,{x_{n - 1}},x_n^*$加密,得到:

$E({x_1}),...,E({x_{i - 1}}),E(x_i^*),E({x_{i + 1}}),...,E({x_{n - 1}}),E(x_n^*).$

随后,将n份密文随机地分成k₁,…,k_n份,模拟p中的分发方法进行分发.

③ S将各个密文随机地分发后对得到的密文做Evaluate运算,得到新的密文:

$E(x_1^*),...,E(x_{i - 1}^*),E(x_i^ \circ ),E(x_{i + 1}^*),...,E(x_{n - 1}^*),E(x_n^ \circ ).$

然后,对所有密文做Evaluate运算,得到:

$E(x') = E(x_1^*)...E(x_{i - 1}^*) \cdot E(x_i^ \circ ) \cdot E(x_{i + 1}^*)...E(x_{n - 1}^*) \cdot E(x_n^ \circ ).$

④ 由于P_n∉P_I,具有概率多项式时间计算能力的S没有ElGamal公钥加密算法的私钥,因此,S不能对密文解密.

在π中:

$\eqalign{ & view_I^\pi (\bar X) = \{ view_1^\pi (\bar X),...,view_{i - 1}^\pi (\bar X),view_{i + 1}^\pi (\bar X),...,view_{n - 1}^\pi (\bar X)\} \cr & {\rm{ }} = \{ ({X_1},...,{X_{i - 1}},{X_{i + 1}},...,{X_{n - 1}}),({x_1},...,{x_{i - 1}},{x_{i + 1}},...,{x_{n - 1}}), \cr & {\rm{ }}{\kern 1pt} (E({x_1}),...,E({x_{i - 1}}),E({x_{i + 1}}),...,E({x_{n - 1}})), \cr & {\rm{ }}(E({{x'}_1}),...,E({{x'}_{i - 1}}),E({{x'}_{i + 1}}),...,E({{x'}_{n - 1}})),E(x),({\sigma _1},...,{\sigma _h})\} , \cr} $

令:

$\eqalign{ & S({X_I},{f_I}(\bar X)) = \{ ({X_1},...,{X_{i - 1}},{X_{i + 1}},...,{X_{n - 1}}),({x_1},...,{x_{i - 1}},{x_{i + 1}},...,{x_{n - 1}}), \cr & {\rm{ }}(E({x_1}),...,E({x_{i - 1}}),E({x_{i + 1}}),...,E({x_{n - 1}})), \cr & {\rm{ }}(E(x_1^*),...,E(x_{i - 1}^*),E(x_{i + 1}^*),...,E(x_{n - 1}^*)),E({x^*}),({{\sigma '}_1},...,{{\sigma '}_h})\} , \cr} $

因为$({\sigma '_1},...,{\sigma '_h}) = ({\sigma _1},...,{\sigma _h}).$由于ElGamal公钥加密算法是语义安全的,任何数据用语义安全的加密算法加密的结果是计算不可区分的,上述模拟过程中得到的消息序列与实际执行过程中得到的消息序列是计算不可区分的,即:

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}$

所以,π在该情况下是保密的.

(2) 云服务器P_n与其他云服务器集合P_I´⊆{P₁,…,P_n-1}合谋想要得到云服务器P_i(P_i∉P_I=P_I´∪P_n)集合X_i中的元素.P_i将其秘密集合X_i编码成x_i并加密为E(x_i),然后将E(x_i)分成k_i份发送给n个云服务器中的k_i个,其他云服务器对于P_i将这k_i份密文发送给了哪k_i个云服务器没有任何信息.云服务器集合P_I不知道收到的关于E(x_i)的份额是否是全部份额,因此,即使P_I将其收到的关于E(x_i)的全部份额相应分量相乘并解密,根据解密后得到的明文也不能确定x_i,从而不能得到关于P_i的机密集合X_i.在协议执行后,除P_i外的其他全部云服务器合谋可能会得到关于X_i的信息,因为P_n与P_I´根据{σ₁,…,σ_h}与集合X₁,…,X_i-1,X_i+1,…,X_n的关系得出关于x_i的信息,但是由于集合{σ₁,…,σ_h}中不同元素只出现一次,因此其他云服务器只会得到集合X_i独有的元素,但这与借助于可信的第三方的理想模型的执行结果是一样的,不会泄露更多的信息.所以,该情况下存在概率多项式时间算法S(S根据情形(1)容易构造,在此省略其构造过程)对于I使得下式成立:

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}$

(3) 云服务器P_n与其他云服务器集合P_I´⊆{P₁,…,P_n-1}合谋,想要得到云服务器集合${P_{\bar I}} = \{ {P_1},...,{P_n}\} - {P_I}$(I= I´∪n)中云服务器集合的元素.当${P_{\bar I}}$中只有一个元素时,不妨令除P_i外的其他云服务器合谋想要得到集合X_i中的元素,这与情形(2)中的情况类似,与借助于理想模型的结果一样.当${P_{\bar I}}$中有两个元素时,不妨令除P_i,P_i+1外的云服务器合谋想要得到集合X_i,X_i+1的元素,最终,他们只能得到关于x_i,x_i+1的不定方程:x=x₁,…,x_i,x_i+1,…,x_n,因此得不到x_i,x_i+1的具体值,即,不能得到关于P_i,P_i+1的集合X_i,X_i+1中的元素.当${P_{\bar I}}$中的元素多于两个时,情况与有两个元素时类似.因此,云服务器集合P_I合谋得不到${P_{\bar I}}$中云服务器集合中的元素.所以,该情况下也存在概率多项式时间算法S(根据情形(1)容易构造S,在此省略具体的构造过程)对于I使得下式成立:

${\{ S({X_I},{f_I}(\bar X))\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}\mathop \equiv \limits^c {\kern 1pt} {\kern 1pt} {\kern 1pt} {\{ view_I^\pi (\bar X)\} _{\bar X \in {{({{\{ 0,1\} }^*})}^n}}}$

因为解决的问题不完全相同,要比较不同方案的计算复杂性是困难的.以上协议1、协议2给出的方案均可以借助于半可信的云服务器进行保密地计算,不再需要做复杂的加密计算,效率较高.为了与现有协议进行比较,下面给出的均是在不借助半可信云服务器计算情况下的效率分析.

在协议1中,n个云服务器中的每个云服务器都需要对其向量中的m个分量加密,共需要加密m⋅n次;最终,参与者P_n需要将经Evaluate运算后的密文向量E(U´)解密,需要解密m次.每个云服务器需要将自己的密文向量随机地分成k份发送给k个云服务器,需要传递m⋅n⋅k个密文,每个云服务器将其收到的密文向量经Evaluate 运算后发送给P_n,需要传递m⋅n个密文,因此共需要传递n⋅m⋅(k+1)个密文.

协议2中,n个云服务器需要将其构造的机密数加密,共需要n次加密;最终,只需要云服务器P_n解密x.每个云服务器需要将自己构造的密文分成k份发送给k个云服务器,需要传递nk个密文;随后,每个云服务器需要将其收到的密文做Evaluate运算,然后将计算后的密文发送给P_n,需要传递n个密文;则共需要传递n(k+1)个密文.在以往保密计算集合并集问题的解决方案中,即使不需要保密,其计算复杂度与通信复杂度也与云服务器拥有的元素个数相关.该方案的计算复杂度与通信复杂度仅与参与者的个数线性相关,而与云服务器集合中元素的个数无关,效率较高.

文献[21]保密计算集合并集的方案是借助全同态加密算法和多项式求值给出的,方案中需要计算n²l次加密运算与nl次解密运算(l表示n个参与者拥有元素的总数),参与者之间需要传递n²l个密文,而现有的全同态加密算法的效率较低.

保密计算集合的并集问题协议比较见表 1,其中,E,D分别表示本文中用到的ElGamal公钥加密算法加密、解密时的运算量,E_F,D_F表示文献[21]中使用的全同态加密算法.

4 保密计算集合的交集

P₁,…,P_n分别拥有秘密集合X₁,…,X_n⊂U={u₁,…,u_m}(u₁＜…＜u_m),他们想要知道X=X₁∩…∩X_n而不想泄露{(P₁,X₁),…,(P_n,X_n)}.保密求集合的交集是隐私保护中一个非常重要的问题,在隐私保护的商业服务、隐私保护的数据挖掘等方面有着重要的应用,但现有的方案效率比较低,且不适用于云计算环境.本文给出一种高效保密计算集合交集的解决方案,该方案经过简单改造也可以应用于云安全计算环境,此处仅给出一般情况下保密求集合交集的方案,(见如协议3).

协议 3. 保密计算集合交集.

输入:P₁,…,P_n各自的秘密集合X₁,…,X_n⊂U={u₁,…,u_m};

输出:X=X₁∩…∩X_n.

1. P_n保留私钥sk,将公钥pk,系统参数params和素数集合P={p₁,…,p_n}公布;

2. 每个参与者P_i(i=1,…,n)计算如下:

(1) 将秘密集合X_i编码为0-r向量U_i(集合X_i中存在的元素在向量U_i的对应位置编码成0,其他位置编码成一个随机数);

(2) 借助哥德尔编码将向量U_i编码成自然数x_i;

(3) 用P_n的公钥pk加密x_i为E(x_i),将E(x_i)随机地分成k_i份发送给n个参与者中的k_i个;

(4) 对收到的所有密文做Evaluate运算得到新的密文$E({x'_i})$并发送给P_n;

3. P_n计算如下:

(1) 对所有收到的密文做Evaluate运算,得到E(x);

(2) 用私钥sk解密E(x)得到x,然后根据算术基本定理展开得到向量U´;

(3) 根据U´中0的分量得到交集X=X₁∩…∩X_n;

(4) 将X公布.

协议3中保密计算集合交集的方案是在协议2的基础上经过简单改造得来的,即:将原本向量U_i中取0的位置改为随机数,而将原本取随机数的位置改为0,并根据U´中0的分量得n个集合的交集.在协议1中,将原本取1(0)的位置改为随机数,原本取随机数的位置改为1(0).最后,根据U´中1(0)的分量也可以得n个集合的交集.

推论. 保密计算集合交集协议是保密的.

根据定理2的安全性证明,该推论的安全性很容易证明,在此省略证明过程.

5 结论

集合隐私计算是许多保密计算的基础,具有广泛的应用.本文给出的云计算环境下的集合隐私计算方案包括多个集合并集的保密计算方案与多个集合交集的保密计算方案.本文首先在云计算环境下设计了基于1-r编码方法与同态加密算法的集合计算方案,该方案效率较高且适用于任何全序关系对象的集合计算.随后,又借助0-r编码方法和哥德尔编码的思想设计了一个高效编码方法,根据高效编码方法给出了一种高效的云集合并集保密计算方案.利用1-r(0-r)编码方法,避免了进行两两计算所导致的信息泄露,也可以借助于半可信的云实现保密计算,而不泄露参与者的信息,降低了集合计算的计算复杂性,特别是可以进行预处理,大大降低了在线计算量.如果将生成的并集按照从大到小的顺序排列,这样的协议还可以保密地对多个集合的所有元素进行排序.

本文构造的云计算环境下的集合隐私计算方案均是属于有限范围内的.对于输入范围未知的集合隐私计算问题,参与者可以将拥有集合中的元素划分为不同的所属范围,然后再按照本文的方法对不同范围内的元素进行保密计算,进而得到参与者集合的隐私计算.但该方法对参与者集合中元素的信息有较多的泄露,因此,研究云计算环境下无限范围内的集合隐私计算问题是我们进一步研究的问题.