0 引言

随着信息技术和互联网技术的发展,人们在享受高效,便捷信息服务的同时,更加注重信息的安全性和隐私性。许多应用场景需要在互不信任的参与者之间共享隐私数据或对隐私数据进行操作。如何保障开放网络环境下用户数据的安全存储和计算成为非常紧迫和严峻的问题。安全多方计算(Secure Multi-Party Computing,SMC)作为密码学领域重要的组成部分,能够有效解决上述问题。文献^[1]首先提出安全两方计算概念,随后Goldreich等^[2-3]进一步对安全多方计算理论进行研究,奠定了安全多方计算的理论基础,证明了任何多方隐私保护计算问题在理论上都是可解的，并提出了通用的解决方法。张恩等^[4]结合博弈论和密码学理论,提出了一种理性的安全两方计算协议,能够保证安全两方计算的公平性。其中隐私集合比较(Private Set Intersection,PSI)作为安全多方计算的一个特例,成为研究的热点,受到越来越多学者的关注。PSI主要解决多个参与方如何在保护自己隐私信息的前提下进行协作计算,获得各方信息的交集,而不泄露除交集之外的任何隐私信息。PSI在隐私数据挖掘^[5]、国土安全^[6]、人类基因组研究^[7]、社交网络^[8]、隐私保护的用户匹配^[9]等方面有着广泛的应用。但PSI作为安全多方计算领域^[10-11]中的重要组成部分,目前的研究还存在一些问题。

Freedman等^[12]基于不经意多项式估值(Oblivious Polynomial Evaluation,OPE)提出了首个隐私集合比较协议,但协议需要参与者之间进行交互且参与者的计算量较大。Niu等^[13]利用交换加密,提出了一种权重感知隐私保护的基于近邻的MSN朋友发现协议。然而,现有交换加密均是确定性加密方案,因此不能很好地保证参与者的隐私性和安全性。文献^[14]

提出的协议建立在决策性Diffie-Hellman 假设(Decisional Diffie-Hellman Assumption,DDH)基础上,计算复杂度是线性的；但该协议是单向的,只有一方知道最终的交集结果，且不能抵御恶意攻击。文献^[15]提出了一种基于多项式估值和同态加密的协议。该协议也是单向的,只有客户端知道交集,服务器端不能获取任何交集信息；协议的复杂度是线性的,但协议基于半诚实模型,不能抵御恶意敌手的攻击。文献^[16]在Freedman协议^[12]的基础上提出了针对恶意敌手和隐蔽敌手的高效、安全的协议。文献^[17]在参与者交互过程中使用相同的密钥来计算伪随机函数,协议效率较高,但因使用对称密钥,安全性不高,容易受到窃听攻击，且该协议要求伪随机函数输入域的大小是多项式。文献^[18]提出了一种服务器辅助的PSI协议,协议针对恶意敌手、半诚实敌手以及隐蔽敌手,首次将PSI应用于亿级大数据的处理上,且不会泄露交集的长度。文献^{[7, 11, 18]}主要存在两方面的缺陷:1)当服务提供者与参与者进行合谋时,即使是在半诚实的条件下,也无法实现基于仿真的安全；2)所有的参与者均使用相同的对称密钥,因此协议不能抵御较弱的窃听敌手的攻击。文献^[19]采用布鲁姆过滤器(Bloom Filter,BF)^[20]和同态加密相结合的方式,将PSI外包到云上实现安全计算,但是协议需要多次同态计算,当比较集合过大时,会对计算的效率产生影响,协议的计算复杂度为O(kω²)；另外协议使用标准的布鲁姆过滤器,在处理数据时,会产生误判,即把原本不属于集合的元素误判为属于这个集合,误判率为: p=1-(1-1/m)^kn。Dong等^[21]针对标准布鲁姆过滤器查询算法存在的元素查询不精确问题,改进了标准的布鲁姆过滤器,提出混淆布鲁姆过滤器的概念。避免了标准布鲁姆过滤器查询算法中元素误判的情况。该协议的复杂度是线性的,可以很好地应用于大数据环境下。

布鲁姆过滤器具有空间复用率高、资源消耗小的特点,与传统的存储算法相比,大大节约了存储空间,还具备计算复杂度低、并行程度较高等优势,具有很高的实用价值。但是标准的布鲁姆过滤器在使用中,存在一定的假阳性率,即产生数据的误判。本文在Dong等^[21]提出的混淆布鲁姆过滤器基础上构造方案。虽然混淆的布鲁姆过滤器(Garbled Bloom Filter,GBF)传输高效,而且解决了标准布鲁姆过滤器误判的问题,但是Dong协议是单向的,只有一方能得到最终的结果,且不能应用到云计算环境中。为了解决这些问题,本文方案引入云外包代理不经意传输协议,代理者作为云服务器参与运算,云租户之间无需进行交互,计算负荷大大减轻;并且云租户不必实时在线,与云服务器交互完成后就交由云服务器进行数据的处理和计算;云租户可以随时随地获取集合比较的结果。本协议结合混淆布鲁姆过滤器与不经意传输,首先使用混淆布鲁姆过滤器来存储云租户的隐私数据,利用密钥共享的性质达到数据安全的目的,使得数据的传输更加安全、高效;然后利用代理的不经意传输协议,云租户分别将数据隐秘的传输给云代理者,代理者并不会得到关于数据的任何有用的信息,保护了云租户的数据隐私;最后,代理者计算出云租户数据集合交集的布鲁姆过滤器,并将其公平的发送给参与各方,云租户对数据进行分析,得到最终的交集信息。

1 预备知识 1.1 布鲁姆过滤器

作为一种简洁的数据表示方法,布鲁姆过滤器(BF)能够满足资源的高效存储和查询需求。布鲁姆过滤器是一个表示位串的空间高效的概率数据结构,它支持元素的哈希查询,可以用来测试一个元素x是否包含在集合S中。其算法结构的本质是将集合中所有元素通过k个哈希函数映射到位串向量之中,不同于传统的哈希存储表,在布鲁姆过滤器中,哈希表退化成一个位串向量V,每一个元素只占用为数不多的比特位。传统的树形查询和哈希查询算法的存储空间与元素自身大小以及集合的规模直接相关,而BF查询算法的存储空间与两者无关,仅仅和元素映射到向量中的位数有关系。一个布鲁姆过滤器是一个m bit的数组,可以表示一个最多有ω个元素的集合S。布鲁姆过滤器使用k个相互独立且均匀选取的哈希函数H={h₁,h₂,…,h_k},其中,H_i:{0,1}^*→{0,1,…,m-1}(1≤i≤k)。BF_m,k(S)表示把集合S映射到由(m,k)构成的布鲁姆过滤器。标准布鲁姆过滤器查询算法如下:设集合S有n个元素，S={s₁,s₂,…,s_n},通过k个哈希函数映射到k个相对应的值,即布鲁姆过滤器中存储元素的相应位置。

元素插入操作,即把元素插入到集合之中:

1) 计算元素x的k个哈希值,即h₁(x),h₂(x),…,h_k(x),这k个哈希值即为所对应的布鲁姆过滤器中的k个位置。

2) 把布鲁姆过滤器的k个位置设置为1,即BF[h₁(x)],BF[h₂(x)],…,BF[h_k(x)]=1。

元素查询操作,即查询元素是否在集合之中:

1) 计算元素x的k个哈希值,即h₁(x),h₂(x),…,h_k(x)。

2) 检查布鲁姆过滤器向量中对应的这k个位置:BF[h₁(x)],BF[h₂(x)],…,BF[h_k(x)]是否都为1。如果任意一位的值为0,则说明该元素不在集合之中。由于误判率的存在,不属于集合的元素可能会误判为属于该集合,即全部位置的值都为1,也不能说明元素就一定在集合中。用P表示向量V中任意一个比特为0的概率。假设哈希函数是均匀分布的,则当集合中的所有元素映射完毕之后,布鲁姆过滤器任意一位为0的概率为:

$P={{\left( 1-\frac{1}{m} \right)}^{kn}}\approx {{e}^{-kn/m}}$

(1)

当不属于集合的元素误判为属于集合时,需要满足每一个对应位的值都为1,即元素的误判率为:

${{f}^{BF}}(m,k,n)\approx {{(1-p)}^{k}}$

(2)

即

$\begin{align} & {{f}^{BF}}(m,k,n)={{(1-p)}^{k}}={{(1-{{e}^{-kn/m}})}^{k}} \\ & \ \ \ \ =\exp \left( k\ln (1-{{e}^{-kn/m}}) \right) \\ \end{align}$

(3)

如果规定了误判率的上限f₀,则在布鲁姆过滤器长度m和哈希个数k一定时,可以通过式(3)计算出布鲁姆过滤器最多可以表示的元素个数n₀:

${{n}_{0}}=-\frac{\ln (1-{{e}^{\ln {{f}_{0}}/k}})\cdot m}{k}$

(4)

k值会对布鲁姆过滤器的误判率产生双重的影响：一方面,k值的增加使得映射的位置变多,误判率会相应下降；另一方面,映射位置的增多会使得布鲁姆过滤器稠密度增加,误判率会相应地增长。实验结果表明,当k值满足式(5)时,布鲁姆过滤器的误判率最小:

$k=\left\lfloor \ln 2(m/n) \right\rfloor $

(5)

1.2 Dong方案的回顾

标准的布鲁姆过滤器在进行数据查询时存在误判率高、数据处理不精准等问题,因此不能直接将集合映射到布鲁姆过滤器中进行存储和查询。针对上述问题,Dong等^[21]提出了混淆的布鲁姆过滤器(GBF)来对数据进行存储和比较,降低了误判率,且协议效率较高。Dong等提出的隐私集合比较方法如下:

步骤1 参与者S首先建立一个混淆的布鲁姆过滤器并且初始化每一个位置的值为空。添加元素x∈S(x=s₁,s₂,…,s_v),S首先将经过加密的元素拆分成k个子份额,对每个元素进行哈希操作得到k个索引值h_i(x),1≤i≤k,1≤h_i(x)≤m。然后分别储存这些子份额在混淆的布鲁姆过滤器对应的位置上。这样建立起来的布鲁姆过滤器称之为混淆的布鲁姆过滤器(GBF)。

步骤2 参与者C建立一个标准的布鲁姆过滤器并将其初始化,当添加一个元素y∈C( y=c₁,c₂,…,c_ω)时,将每个元素进行与S相同的哈希取值,得到k个索引值h_i(y),然后将布鲁姆过滤器对应位置的索引值设置为1,其他的设为0,例如,BF_C[h_i(y)]=1。

步骤3 如果一个元素确实属于C∩S,那么对于C所对应的每一个布鲁姆过滤器位置i,如果BF_C[i]值为1,则S所对应的GBF_S[i]为元素x的子份额。因此,通过算法1,所有x的子份额能够拷贝到另外一个新的混淆的布鲁姆过滤器中,即新的混淆布鲁姆过滤器编码了两个集合的交集。

步骤4 参与双方通过对比自身的布鲁姆过滤器和新的混淆的布鲁姆过滤器计算出交集信息。

算法1 GBFIntersection(GBFs,BFs,m)。

输入 An (m,n,k,H,λ)-garbled Bloom filter GBFs,an (m,n,k,H)-Bloom filter BF_C,m

输出 An (m,n,k,H,λ)-garbled Bloom filter GBF_C∩S

For i=0 to m-1 do

 If BF_C[i]==1 then

  GBF_C∩S[i]=GBF_S[i];

  Else

   GBF_C∩S[i]←r{0,1}^λ;

  End

 End

1.3 代理不经意传输

为了将Dong方案有效地扩展到云计算环境中,方案引入非交互代理不经意传输(Proxy Oblivious Transfer,POT)^[22]概念,该协议是Naor协议^[23]的一个改进。在代理不经意传输协议中,共有三方:一个发送方、一个选择方和一个代理方。发送方持有输入信息(x₀,x₁),选择方持有一个选择比特b。最终,代理方了解到x_b的值(并且不知晓x_1-b),发送方以及选择方什么信息也得不到。

非交互的密钥交换：一个非交互的密钥交换协议允许两个参与方通过他们各自的公钥产生一个共享的密钥而无需经过任何的交互。令KEA₁、KEB₁代表密钥产生算法,产生参与双方各自的公私钥对(pk_a,sk_a)、(pk_b,sk_b)。存在算法KEA₂、KEB₂，使得KEA₂(pk_b,sk_a)=KEB₂(pk_a,sk_b)。Diffie-Hellman的密钥交换协议是一个具体的实例。

基于密钥交换的代理不经意传输：主要思想是发送方和选择方在参数设置阶段利用密钥交换技术共享一个随机的数值。然后,利用共享的随机数值(代理方并不知情),参与双方可以运用一次高效的加密方式传输他们的信息，其中Prf为伪随机函数。算法过程如下:

(pk_S,sk_S)←SetupS(1^κ)。发送方运行密钥产生算法,产生自身的公私钥对(pk_a,sk_a)←KEA₁(1^κ),设pk_S:= pk_a,sk_S:=sk_a。

(pk_C,sk_C)←SetupC(1^κ)。接收方运行密钥产生算法,产生公私钥对(pk_b,sk_b)←KEB₁(1^κ),设pk_C:= pk_b,sk_C:=sk_b。

α←Snd(i,pk_C,sk_S,x₀,x₁)。令ke代表密钥交换协议的输出,例如,ke:=KEA₂(pk_C,sk_S),z₀、z₁代表两个由伪随机置换算法产生的两个随机串,只有参与者知道z₀、z₁的值。它用来对明文进行加密运算,隐藏明文的信息,以此来保证参与者信息的隐私性和安全性。κ是安全参数。发送方计算(z₀,z₁,π):=Prf_ke(i),其中：|z₀|=|z₁|=κ,π∈{0,1}。设α:=(α₀,α₁),其中：α_π=z₀⊕x₀,α_1⊕π=z₁⊕x₁。

β←Chs(i,pk_S,sk_C,b)。令ke代表密钥交换协议的输出,例如,ke:=KEB₂(pk_S,sk_C)。接收方计算(z₀,z₁,π):=Prf_ke(i)，其中：|z₀|=|z₁|=κ,π∈{0,1}。接下来仅仅发送和选择比特b相关的部分,即β:=(b⊕π,z_b)。

y=Prx(i,pk_S,pk_C,α,β)。代理方解析数据α:=(α₀,α₁),β:=(b⊕π,z_b)。计算出最终结果y:=α_b′⊕z′。协议满足正确性和高效性。密钥交换的输出和伪随机函数看起来都是随机的,因此发送方隐私信息可以得到保障。协议同样还针对代理者隐藏了接收方的选择比特。

2 云外包隐私集合比较协议

本文提出一种基于混淆布鲁姆过滤器的云外包隐私集合比较协议。该协议使用混淆的布鲁姆过滤器作为存储参与者集合信息的一种数据结构,弥补了标准布鲁姆过滤器直接进行集合计算所带来的信息泄露问题,使得集合与集合之间数据匹配更加精确；并且布鲁姆过滤器作为一个空间利用率较高的数据结构,能够满足大量数据的存储而不占用太多的资源,提高了信息存储和查询的效率；协议还引入第三方代理对信息进行运算,大大降低了参与双方自行进行集合运算所带来的开销，解决了频繁交互产生的数据安全问题；使用不经意传输协议,使得代理者在对云租户数据进行计算的时候,无法获知真正的数据信息,防止了信息的泄露。协议的流程如下:云租户在协议开始前进行一次协商产生相关参数后,分别把各自的数据添加到布鲁姆过滤器之中,然后把计算结果发送给代理者；代理者执行不经意传输协议对信息进行处理和计算,把计算结果添加到一个新的混淆布鲁姆过滤器中,并把结果发送给云租户；最后,云租户通过对比布鲁姆过滤器,得到集合交集的信息。

初始化参数设置:云租户S和云租户C协商一个随机数l,用该随机数对集合元素进行加密,例如:

S={a₁‖l,…,a_v‖l}={s₁,s₂,…,s_v}

C={b₁‖l,…,b_ω‖l}={c₁,c₂,…,c_ω}

其中:v、ω分别代表云租户S和云租户C集合元素的个数。

设布鲁姆过滤器的长度为m,H={h₁,h₂,…,h_k}代表k个哈希函数,λ是安全参数。

隐私集合比较协议:

步骤1 (pk_S,sk_S)←SetupS(1^κ):S运行密钥产生算法,(pk_a,sk_a)←KEA₁(1^κ),产生公私钥对pk_S:= pk_a,sk_S:=sk_a。

GBF_S←BuildGBF(S,v,m,k,H,λ):S首先构建一个空的布鲁姆过滤器,然后将元素分别进行k次哈希操作得到k个哈希值。当插入元素x∈S到布鲁姆过滤器GBFs时,先将元素用密钥共享的方式拆分成k个子份额,然后把这k个子份额分别放到k个哈希值所对应的GBFs的对应索引位上。

α←Snd(j,pk_C,sk_S,x_j,x_j′):S运行该算法,在第j(1≤j≤m)次运算过程中,令ke代表密钥交换协议的输出,例如,ke:=KEA₂(pk_C,sk_S),计算(z₀,z₁,π):=Prf_ke(j)。z₀=z₁=κ,并且π∈{0,1},然后建立α:=(α₀,α₁)。

α_π=z₀⊕x_j

α_1⊕π=z₁⊕x′_j

其中:x_j={0,1}^λ,x′_j=GBF_S[j]。

步骤2 (pk_C,sk_C)←SetupC(1^k):C运行密钥产生算法,(pk_b,sk_b)←KEB₁(1^k),产生公私钥对pk_C:= pk_b,sk_C:=sk_b。

BF_C←BuildBF(C,ω,m,k,H,λ):C构建一个空的布鲁姆过滤器,并把集合元素按照标准的布鲁姆过滤器插入算法插入到布鲁姆过滤器中。

β←Chs(j,pk_S,sk_C,b):C运行该算法,令ke代表密钥交换协议的输出,例如,ke:=KEB₂(pk_S,sk_C),计算(z₀,z₁,π):=Prf_ke(j),其中：z₀=z₁=κ并且π∈{0,1}；然后计算β:=(b⊕π,z_b),其中：b=BF_C(j)即布鲁姆过滤器中第j个位置的索引值。

步骤3 Z:=Prx(j,pk_S,pk_C,α,β):在第j次运行过程中,代理者解析α:=(α₀,α₁),β:=(b′,z′),其中：b′=b⊕π,z′=z_b。计算y:=α_b′⊕z′并将计算结果放置在一个新的混淆的布鲁姆过滤器第j个索引位置上,构成GBF_C∩S^π。

3 协议的安全性与性能对比 3.1 安全性证明

针对半诚实的模型下提出的隐私集合比较协议,在三种场景下,分别给出了不同参与方被腐败时的安全性证明。

定理1 基于混淆布鲁姆过滤器的云隐私集合比较协议的安全性基于以下两个场景：1) 一个半诚实的服务器和诚实的参与者；2) 一个诚实的服务器以及一个腐败的参与者。

证明 构建一个模拟器Sim_P,它调用敌手A腐败服务器。接收集合S和集合C的长度信息v和ω，并且模拟一个半诚实的服务器P执行P、S、C之间的协议。Sim_P首先产生两个集合S₁、C₁,S₁=v,C₁=ω，并把它们分别映射到m长度的布鲁姆过滤器GBF′_S、BF′_C上。然后Sim_P使用交换密钥ke并计算伪随机函数Prf_ke(j):=(z′₀,z′₁,π′),令x₁={0,1}^λ,x₂=GBF′_S[j],α_π′=z′₀⊕x₁,α_1⊕π′=z′₁⊕x₂,b₁=BF′[j]。在第j次运算中,Sim_P计算y′:=α_b1⊕π′⊕z′_b1并依次放置在新的布鲁姆过滤器GBF_C′∩S′^π′中,最后,Sim_P将输出结果发送给A,即产生和A一致的输出。根据伪随机函数的性质,协议在真实场景和模拟器场景下是不可区分的。

构建一个模拟器Sim_S调用敌手A腐败参与者S,执行参与者S和C以及服务器P共同参与的协议。首先,Sim_S接收到参与者之间产生的交换密钥ke。当它从S收到信息GBF_S后,计算α:=(α₀,α₁)并把它发送给可信方,随后可信方计算出y:=α_b′⊕z′并返回给Sim_S。Sim_S将其发送给敌手A。最终Sim_S的输出和敌手A的输出是一致的。根据伪随机函数的性质,S的视图以及C的视图在模拟器情形下和真实情形下是不可区分的。

参与者C被腐败的情形与S被腐败的情形类似,这里就不再赘述。综上所述,协议证明是安全的。

3.2 性能对比

协议使用了POT协议和混淆的布鲁姆过滤器，不仅能够高效处理信息时代的庞大数据,而且参与者之间无需交互就能随时随地获取到集合比较的结果。其计算复杂度和空间复杂度为:

计算复杂度 构建布鲁姆过滤器和混淆的布鲁姆过滤器时,每一个参与者需要k·n(n代表参与者元素的个数)次哈希操作；然后,在不经意传输协议中发送方需要进行λ次公钥操作,接收方需要进行2λ次公钥操作,在不经意传输执行过程中参与双方需要m=kn lb e次操作。

空间复杂度 云租户C存储自身的布鲁姆过滤器,最多需要m个比特,云租户S存储混淆布鲁姆过滤器,最多需要λm个比特；云代理者存储参与双方的信息以及最终产生的交集布鲁姆过滤器,共需(1+2λ)m比特。

表 1将本文方案同现有几种经典PSI方案进行了综合对比。

文献^[21]主要利用了不经意传输协议和布鲁姆过滤器来解决PSI中产生的问题,实现了半诚实模型下的高效解决方案,复杂度较低。不足之处在于协议需要参与者之间多次交互进行查询、计算等操作,对于参与者的硬件和网络要求较高,资源开销比较大；协议是两方的,不能实现多方集合比较；而且协议是单向传递的,只有一方能得到最终的计算结果,公平性得不到保障。本文利用文献^[21]所提出的混淆的布鲁姆过滤器算法,结合代理云服务器,采用代理不经意传输协议来实现隐私集合比较。

云租户事先将自身的集合和相关参数交给代理云服务器,在执行过程中云租户之间无需进行交互；协议执行完毕后,代理云服务器将计算结果交给各个云租户,其自身并不知道计算的结果,参与者可在任意时刻和地点获取双方的集合比较结果,无需实时在线,实现了公平性；而且协议可以扩展到多个云租户进行集合比较的情形。文献^[19]研究了半诚实模型和恶意模型下的隐私集合比较问题。在半诚实模型下,使用GM(Goldwasser-Micali)加密协议和SYY(Sander Young Yung)协议来实现同态的加密运算,协议安全性和可靠性较高,但是计算复杂度和通信复杂度大为增加,且参与双方需要进行多次交互才能得到最终结果。文献^[24]引入了权威认证(Certification Authority,CA)这一概念对参与者的集合元素进行认证,确保集合元素的正确性,但最终只有一方能够得到集合比较结果,另一方并不知情,且协议需要参与各方一直保持在线。文献^[25]基于YAO的混淆电路模型来实现隐私集合比较,在计算过程中无需存储所有电路信息,以此来减少通信及计算的开销,且效率较高；但是电路的构建与计算仍然是非常复杂的一个过程,在计算机上模拟简单的电路就需要消耗大量的资源，且参与者需要多次交互,方案也不能应用于多方的情形。文献^[18]引入伪随机函数来计算双方的隐私集合交集,并且协议存在一个不可信的第三方来辅助计算,虽然参与双方之间不需要进行交互,且可以对亿级规模的大数据进行高效的计算,但是由于使用相同的密钥对数据进行加密,安全性较弱,一旦通信信道被敌手窃听,可以很容易地获取参与方的隐私信息。

本文提出的协议结合了混淆布鲁姆过滤器和代理的不经意传输协议。混淆布鲁姆过滤器的性质使得协议可以高效地存储大规模的数据信息而不占用很多的内存空间；引入代理者使得参与双方可以在非交互的情况下计算出隐私集合的交集信息,无需参与者实时在线进行操作；最终,参与各方可以公平地得到计算的结果。

4 结语

Dong的协议使用混淆的布鲁姆过滤器提高了查询的效率和精度,可以应用在大数据处理上，但协议局限性在于传输的单向性以及不能应用在云环境中,且不能扩展到多方。本文在Dong协议^[21]的基础上进行改进,提出了基于混淆布鲁姆过滤器的云外包隐私集合比较协议,不仅能对大数据进行高效的存储和处理,并且云租户在协议执行过程中无需交互,无需实时在线,可随时获得最终的计算结果。协议还引入了云代理服务器进行辅助运算,大大减轻了云租户的计算开销,并且云租户能够公平地获得最终的结果。不足之处在于没有考虑恶意敌手情况下协议的安全性,下一步将协议扩展到多个参与者并考虑恶意敌手存在下的协议安全性。