0 引言

社交网络^[1]是为了方便社会成员进行信息交流而应运产生的一个多功能平台，社交网络服务提供者蕴含和提供了丰富的资源。目前，Facebook、Twitter、Orkut、Myspace、Cyworld等社交网络已经变得十分流行，数据统计发现，Facebook用户每天共享的内容超过40亿，Twitter每天处理的推特数量已经超过3.4亿。移动社交网络的发展，人们可以随时随地在社交网络上发布个人喜欢的视频、图片、文章等信息，使得人与人之间的交流互动变得更加快速便捷。通常来说，互相添加为好友的范围无非是亲戚、同事和同学等线下朋友，然而这并不能较好地满足交流的需要。比如说篮球爱好者喜欢关注篮球资讯、篮球技术等方面的资源，迫切需要找到志同道合的朋友来探讨篮球经验，相互学习借鉴。这就需要社交网络为用户提供好友发现交流的平台，可以让他们根据自身意愿互相添加为好友。然而发布出去的个人属性、地理位置等敏感信息一旦被不法人员利用，其后果不堪设想。为了保护个人隐私安全，现设想了一个应用场景，并采取了一些方法来解决安全问题。

考虑如下一种应用场景：社交网络中存在互不相识的两个社会成员Alice和Bob，Alice发现Bob的兴趣爱好与自己很相近，渴望Bob成为自己线上的朋友，但是面对陌生的对象Alice不愿意将自己的隐私泄露给他人。于是需要在保证各成员隐私安全的前提下实现两者的交流。 我们提出的一种解决方法如下：社交网络中，实际上通信双方不能直接进行交互，需要借助社交网络服务提供者(Social Network Service Provider,SNSP)进行中转。Alice和Bob均可以与SNSP进行通信，而Alice和Bob不能独立通信，如图 1所示。

1) 假设Alice想要查询与自己兴趣爱好相同的朋友，并向SNSP发出申请。

2) SNSP接到Alice的申请后，对符合条件的用户进行初步筛选，并将Alice的兴趣爱好抽象为喜好向量集合，如Alice喜欢关注小说、卡通和电影，抽象出来的向量集合为V_Alice=｛novel,cartoon,movie｝,筛选出来的用户同样抽象为类似Alice的向量集合，如V_Bob=｛basketball,novel,program｝。

3) Alice和Bob分别使用向量集合中的某个向量与对方的对应向量进行模糊匹配，如果匹配成功，则互相加为好友;否则活动结束。

Alice和Bob相对于社交网络服务提供者来说是两个客户端，由于本文方案的构造是针对Alice和Bob而言的，为了方便标记和理解，本文将发起好友请求的Alice作为“客户端”，将筛选出来接受“客户端”请求的Bob作为“服务器”。Alice确定Bob满足了自己的匹配要求后才能申请Bob为好友，Bob同样要确定Alice是否与自己匹配，双方经历了这样的过程才能达到添加好友的目的。

2004年，Freedman等^[2]首次提出了半诚实模型下基于多项式的模糊隐私匹配问题，设计了一个“2-out-of-3”匹配方案，Chmielewski等^[3]认为该方案存在缺陷，证明了客户端能够在没有与服务器端相同元素的前提下获得服务器数据。Ye等^[4]提出了基于交错所罗门码(interleaved Reed-Solomon code)的share-hiding error-correcting秘密共享方案，并构造了基于同态加密的模糊匹配协议。Hazay等^[5]提出了以随机预言机为安全模型、在恶意模型下的隐私集合交集(Private Set Intersection,PSI)协议。Kamara等^[6]在服务器辅助环境中设计了一个可支持十亿元素集合的PSI协议，Abadi等^[7]设计了基于分值的外包可委托的O-PSI协议，它允许多个客户端独立的给服务器上传隐私数据集合，并且能够要求服务器计算出交集。Debnath等^[8]设计了两个基于DDH(Decisional Diffie-Hellman)假设、能够抵抗恶意敌手的PSI-CA(Private Set Intersection CArdinality)协议。Shi 等^[9]首次提出了欺骗敏感量子PSI协议，该方案能够支持大数据,相比以前经典方案更具有较低的通信复杂度。Dong等^[10]提出了分别基于半诚实模型和恶意模型，可支持大数据、高效的PSI协议，其中Oblivious Bloom Filter协议具有线性复杂度。Hahn等^[11]在文献^[10]的基础上结合Merkle tree构造了可以抵抗恶意客户端用户的交集算法，但其效率有较低的退化。本文在文献^[10]的基础上，将交集的生成方法应用于模糊匹配问题中，得到了两个交集公共元素的数量，以此判断两个集合是否匹配成功；其计算复杂度和通信复杂度均能够达到线性，较以前方案效率有较大提高。

1 相关知识 1.1 模糊匹配

在Eurocrypt'04上，Freedman等^[2]提出了有关隐私的模糊匹配问题，其定义是双方分别拥有包含n_C和n_S个向量的集合，每个向量的长度为T，其中一方按照协议将向量集合中的某个向量与对方的对应向量进行运算，计算出交集，如果交集中至少存在t个相同部分，则这两个向量匹配。计算出交集的过程中要保证对方的集合安全且不会泄露任何信息，另一方不能知道交集的内容。

设客户端向量集合C^*={C₁,C₂,…,C_nC}，服务器向量集合S^*={S₁,S₂,…,S_nS}，每个向量都是由长度为T的元素组成，即C_i=(a_i,1,a_i,2,…,a_i,T)(i∈{1,2,…,n_C}，S_j=(b_j,1,b_j,2,…,b_j,T)(j∈{1,2,…,n_S}，当C_i与S_j中有t以上个数的相同元素，则C_i≈_t S_j。

本文方案中，门限值t的大小直接决定匹配的程度和效果，t应当根据客户端与服务器双方的意愿进行设定。设匹配率η=t/T，如果双方要求兴趣匹配率越高，那么设置的t应该越大。

1.2 秘密共享

秘密共享是一个基本的密码学原语，广泛地应用于秘密信息的传递和存储。(t,n)秘密共享方案就是使用者将秘密s分成n份并设置门限值t，对方得到其中t份以上份额便能有效地恢复出秘密s。最为典型的应用方案就是Shamir秘密共享方案^[12]。当t=n时，通过简单的异或操作就可以得到一个高效的(n,n)秘密共享方案^[13]。其原理是使用者生成n-1个与s相同长度的随机比特串r₁,r₂,…,r_n-1，计算出r_n=r₁⊕r₂⊕…⊕r_n-1⊕s，每个r_i都是秘密的组成份额，通过计算r₁⊕r₂⊕…⊕r_n便能够恢复出秘密s，并且少于n个份额的信息时不会泄露任何秘密。

1.3 不经意传输协议

不经意传输协议_l^[14]是一种保护隐私的双方通信协议。它允许发送方以一种保护双方安全的方式将信息发送给接收方，发送方并不知道接收方接收的是哪份消息，接收方也不会泄露发送方发送的其他部分。不经意传输协议可以表示为OT^m，即发送方拥有m对lbit串(x_j,0,x_j,1)(0≤j≤m-1) ，接收方拥有mbit的选择串r=(r₀,r₁,…,r_m-1)。当r_i为0时，选择x_j,r0，否则选择x_j,r1。协议执行的最后结果为向量R=(x_0,r0,x_1,r1,…,x_m,rm)。

但是，不经意传输协议在实际应用过程中开销很大，效率已经成为制约它应用的主要瓶颈。Beaver_l^[15]提出使用单向函数将不经意传输协议进行拓展，即在较小的数据输入情况下获得较大的数据传输量。Ishai等^[16]提出了依赖于随机预言机模型的不经意传输拓展协议，能够将OT^m转化为OT_λ^λ，λ为安全参数。本文在调用Naro-Pinkals不经意传输协议^[17]时，即利用这一良好特性将公钥加密的运算量m减少至λ。

1.4 Bloom过滤器和Garbled Bloom过滤器

Bloom Filters^[18]是一种紧凑的数据结构，支持数据存储和成员查询，实现了mbit的数组来表示最多有n个元素的向量S=(s₁,s₂,…,s_n)。每个Bloom Filters具有k个均匀分布的哈希函数H={h₀,h₁,…,h_k－1}，其映射的值域为[0,m－1]。本文中用(m,n,k,H)-Bloom Filter来表示由(m,n,k,H)确定的参数，用BF_S来表示数据集合S生成的Bloom Filters，用BF_S[i]来表示BF_S中第i个数据位。如图 2所示，初始化时，所有的数据位都被置为0，当插入元素x∈S时，k个哈希函数对x进行运算得到k个索引数，令相应位置为1，即BF_S[h_i(x)]=1，0≤i≤k－1。为了查询y是否在S中，y同样被k个哈希函数运算，得到k个哈希值来检查对应的数据位，如果其中任何一个数据位为0，则y不在向量S中；否则y可能存在于S中。

而Garbled Bloom Filters^[10]是标准Bloom Filters的变形，是概念的引申，其本质没有差异，同样支持成员查询。插入和查询元素与标准Bloom Filters相同。其不同之处在于Garbled Bloom Filters使用的是λbit串而并非0、1比特。本文中，我们用(m,n,k,H,λ)-Garbled Bloom Filter来表示由(m,n,k,H,λ)确定的参数。用GBF_S来表示数据向量S生成的Garbled Bloom Filters，用GBF_S[i]来表示GBF_S中第i个λbit串。

1.5 半诚实模型

半诚实模型^[19]中，静态的半诚实敌手A控制着参与双方中的一方，并且严格按照协议的条件准确执行。敌手A可以通过另一方的输入推导出更多信息，但是不能对信息进行修改。

设协议π计算出一个输入映射为输出的函数f：{0,1}^*×{0,1}^*→{0,1}^*×{0,1}^*，f=(f₁,f₂)。对于每一对输入x,y∈{0,1}^*来说，其输出为随机变量(f₁(x,y),f₂(x,y))，其中一方获得f₁(x,y)，另一方获得f₂(x,y)。

在模型中，A如果通过协议中的一方计算出来的任何信息只能从输入与输出中获得，那么协议π是安全的。半诚实模型可以通过模拟来形式化表示。协议执行过程中，如果参与方的视图被模拟时只考虑输入与输出，那么参与方i的输入(x,y)在协议π执行过程中可以表示为view_i^π(x,y)=(w,r₁ⁱ,mⁱ,…,m_tⁱ)，其中w∈(x,y)是i的输入，r_jⁱ是i内部随机硬币投掷值，mⁱ表示i接收的第j份消息。 定义1 半诚实模型。设f=(f₁,f₂)是确定性函数，如果存在多项式时间的方案Sim₁和Sim₂，即：

$\begin{align} &{{\left\{ \text{Si}{{\text{m}}_{1}}\left( x,{{f}_{1}}\left( x,y \right) \right) \right\}}_{x,y}}\overset{c}{\mathop{\equiv }}\,{{\left\{ \text{View}_{\text{1}}^{\pi }\left( x,y \right) \right\}}_{x,y}} \\ &{{\left\{ \text{Si}{{\text{m}}_{2}}\left( y,{{f}_{2}}\left( x,y \right) \right) \right\}}_{x,y}}\overset{c}{\mathop{\equiv }}\,{{\left\{ \text{View}_{2}^{\pi }\left( x,y \right) \right\}}_{x,y}} \\ \end{align}$

那么协议π在静态半诚实敌手存在情况下是安全的计算函数f。

2 半诚实模型下的简单方案

此方案的安全性建立在半诚实模型下，参与双方(客户端与服务器)诚实的参与协议，可以记录协议执行的中间结果，同时也可以用中间结果推导出有用信息，但是不能对有用信息进行修改。假设客户端与服务器分别拥有向量集合C^*={C₁,C₂,…,C_nC}，S^*={ S₁,S₂,…,S_nS}，本文中模糊匹配的操作对象是针对C^*中的某个向量C_i与S^*中的某个向量S_j进行作用。为了字符标识方便，下文中将直接使用C和S作为向量，那么客户端对向量C生成BF_C，服务器对向量S生成GBF_S，客户端将BF_C与GBF_S进行作用产生交集GBF_C∩S，将C中的元素作为查询元素对GBF_C∩S进行查询，记录查询成功的个数。如果个数大于或等于门限值，则客户端输入向量C与S成功匹配，否则匹配失败。

2.1 协议初始建立阶段

首先介绍GBF_S(S,m,k,H,λ)生成算法，具体如算法1所示。如图 3所示，当插入x₁时，x₁被分为s₁¹，s₁²，s₁³，分别存放在相应位置。当插入x₂时，GBF_S^[3]已经被x₁的份额占据，于是保持该位置值不变，利用s₁²生成s₂¹，s₂²，使得x₂=s₂¹⊕s₂²⊕s₁²。同理，当插入x₃时，也按照上述方法解决。当所有元素都已经存放完毕时，则对Garbled Bloom Filters进行遍历，如果存在空位，则随机产生λbit串填充。当需要查询某个元素y时，同样用哈希函数进行运算，找到所有对应的比特串进行异或操作恢复出recovered值。如果recovered与y相同，则说明y∈S，否则y∉S。其如算法2所示。

算法1  GBF(S,n,m,k,H,λ)生成算法。

输入 数据向量S，向量元素个数n，Bloom Filter位置个数m,哈希函数个数k,H={h₀,h₁,…,h_k-1},安全参数λ；

输出 An(m,n,k,H,λ)-Garbled Bloom Filter GBF_S。 GBF_S=new m-element array of bit strings

for i=0 to m-1 do

GBF_S=NULL；//将m个位置赋空值

end

for each x∈S do //插入x

emptySlot=-1,finalShare=x；

for i=0 to k-1 do

j=h_i(x)；//将x哈希为k个索引值

if emptySlot==-1 then

emptySlot=j;

else

GBF_S←{0,1}^λ；//随机生成λbit串

finalShare=finalShare⊕GBF_S；

end

else

finalShare=finalShare⊕GBF_S；

end

end

GBF_S=finalShare；

end

for i=0 to m-1 do

if GBF_S=NULL then //遍历后空位随机填补

GBF_S←{0,1}^λ； //λbit串

end

end

算法2  GBF(GBF_S,y,k,H)查询算法。

输入 GBF_S,元素y,哈希函数个数k,H={h₀,h₁,…,h_m-1}；

输出 如果y∈S则返回正确,否则返回错误。

recovered={0}^λ；

for i=0 to k-1 do

j=h_i(y)；

recovered=recovered⊕GBF_S；

end

if recovered==y then

return true；

else

return false；

end

2.2 协议执行过程

客户端将自己产生的BF_C与GBF_S作用生成GBF′_C∩S，当BF_C[i]为1时，令GBF′_C∩S[i]=GBF_S[i]，否则随机生成比特串进行填充。文献^[10]已经证明了由C∩S生成的GBF_C∩S=GBF′_C∩S，此处不再详细论述。协议执行的算法具体如算法3。算法3中，第3行到第6行使用到了不经意传输协议。客户端将BF_C作为选择参数参与OT_λ^m协议。服 务器扮演发送方发送m对λbit串(x_i,0,x_i,1)，x_i,0是随机生成的字符串，而x_i,1是GBF_S[i]。当BF_C[i]为0时，客户端收到随机字符串；当BF_C[i]为1时，客户端收到GBF_S[i]。由不经意传输协议OT_λ^m生成的最终结果为GBF_C∩S^π=GBF_C∩S，文献^[10]已经证明了该等式的正确性，此处不再赘述。

算法3  GBFIntersection(GBF_S,BF_C,m)交集生成算法。

输入 参数(m,n,k,H,λ)GBF_S,参数(m,n,k,H)BF_C,Bloom Filter位置个数m；

输出 An (m,n,k,H,λ)-Garbled Bloom Filter GBF_C∩S。 GBF_C∩S=new m-element array of bit strings;

for i=0 to m-1 do

if BF_C==1 then

GBF_C∩S=GBF_S;

else

GBF_C∩S←{0,1}^λ;

end

end

客户端利用BF_C中元素进行查询的过程其实就是恢复出双方交集的过程，其算法具体如算法4所示。客户端将自己的集合作为查询的对象对GBF_C∩S进行查询，通过GBF_C∩S恢复出来的元素与查询的对象如果相同，则说明有一个元素匹配成功。算法中matchnumber记录能够恢复成功的数量，最后来判断交集个数，若大于等于门限值t，则说明两个向量是匹配的；否则说明两个向量不匹配。

算法4  IntersectionMatch(GBF_C∩S,C,t,H)模糊匹配算法。 输入 GBF_S,元素C,哈希函数个数k,哈希函数H={h₀,h₁,…,h_k-1}；

输出 如果matchnumber≥t返回正确,否则返回错误。 recovered={0}^λ,matchnumber=0;

for j=0 to k-1 do

location=h_j(C);

recovered=recovered⊕GBF_S;

end

if recovered==C then

matchnumber++;

end

if matchnumber≥t then

return true;

else return false;

end

3 方案分析 3.1 安全性分析

本文方案的安全性依赖于双方交集生成过程的安全性以及用客户端元素进行查询交集GBF_C∩S的安全性。上述方案在半诚实模型下安全，现给出方案的安全性证明。

定理1  设C、S分别是预定义的域，f_∩是交集函数，f_∩为两交集中共同元素的个数，那么C与S匹配的表达式为：

$\begin{align} &true=\left\{ \left| {{f}_{\cap }}\left( C,S \right) \right|\ge t \right\}=\left\{ \left| \left( {{f}_{C}}(C,S),{{f}_{C}}(C,S) \right) \right|\ge t \right\} \\ &=\left\{ \left| \left( C\cap S,\wedge \right) \right|\ge t \right\} \\ \end{align}$

假定不经意传输协议OT_λ^m是安全的，则算法3能够安全地计算f_∩，算法4得出匹配的结果是正确且安全的。

证明 如果OT_λ^m是安全的，则发送者和接收者的模拟器保证存在，现利用这两个模拟器作为子程序构建出新的模拟器。

服务器视图 假设服务器遭到破坏后成为了恶意用户。本文构建了模拟器Sim_S，协议中它可以接收服务器的秘密输入和输出，生成服务器的视图。对于S来说，模拟器Sim_S均匀选取随机投掷硬币的结果r^S，并且生成GBF_S。然后Sim_S调用OT发送者Sim^OT的模拟器，最后Sim_S输出模拟视图(S,r^S,Sim^OT(GBF_S,∧))。真实协议执行的视图包括输入S，随机投掷硬币结果，以及协议中的消息。在模拟视图中，输入向量S与真实执行视图中的对应向量相同，随机投掷硬币的结果也是均匀选取，因此其分布与真实执行情况相同。如果OT协议是安全的，那么由Sim_snd^OT(GBF_S,∧)产生的视图分布与真实OT协议执行的视图分布具有不可区分性。因此可以得出结论：模拟视图与真实视图不可区分。

客户端视图 构建模拟器Sim_C，它可以接收秘密输入C和输出C∩S。Sim_C选择随机投掷硬币结果r^C，分别生成BF_C和GBF_C∩S，然后用BF_C和GBF_C∩S调用接收者的模拟器Sim^OT。Sim_C获得OT协议的视图，输出模拟视图(C,r^C,GBF_C∩S,Sim^OT(BF_C,GBF_C∩S))。真实协议执行视图包括输入向量C、随机硬币投掷结果r^C、GBF^π，以及协议中的消息。模拟视图中，输入向量C和硬币投掷结果r^C与真实视图对应部分不可区分，GBF_C∩S与GBF^π也是不可区分的。如果OT协议是安全的，那么模拟视图与真实视图OT协议中的消息也是不可区分的。因此可以得出结论：模拟视图与真实视图不可区分。

综上所述：

$\begin{align} &{{\left\{ Si{{m}_{S}}\left( S,{{f}_{S}}\left( C\cap S \right) \right) \right\}}_{C,S}}\overset{c}{\mathop{\equiv }}\,{{\left\{ \text{view}_{S}^{\pi }\left( C,S \right) \right\}}_{C,S}} \\ &{{\left\{ Si{{m}_{C}}\left( C,{{f}_{C}}\left( C\cap S \right) \right) \right\}}_{C,S}}\overset{c}{\mathop{\equiv }}\,{{\left\{ \text{view}_{C}^{\pi }\left( C,S \right) \right\}}_{C,S}} \\ \end{align}$

以上证明了C与S生成交集GBF_C∩S的安全性，因此客户端用与GBF_C∩S作用后得出相同元素个数的过程也是安全的，所以该方案安全性得证。

3.2 复杂度分析

该协议使用了OT_λ^m协议，其效率主要决定于OT传输协议。如果调用Ishai等^[16]构造的半诚实模型下的OT扩展协议以及Naor-Pinkas^[17]传输协议，则：

计算复杂度 为了构建BF_C和GBF_C∩S，服务器和客户端都需要k·n次哈希操作。对于Naor-Pinkas不经意传输协议，双方分别需要λ次和2λ次公钥运算操作。对于OT扩展协议，双方都需要m=kn lb e≈1.44kn次哈希操作。用C查询交集GBF_C∩S找出相同元素时，客户端需要k·n次哈希操作。

存储复杂度 客户端需要存放BF_C和GBF_C∩S，因此共需要(λ+1) mbit，服务器端需存放GBF_S，因此需要λ·mbit。如果忽略运算过程中暂时占用的存储空间，则共需要(2λ+1) mbit。当Bloom Filters的存放位置数量确定后，存储复杂度仅与安全参数λ有关，且随着λ呈线性变化。

通信复杂度 服务器扮演发送者的角色通过不经意传输向客户端发送数据，此过程中需要发送m对λ比特串(x_i,0,x_i,1)，因此需要2λ·mbit通信量，其他的通信开销因为比较小可以忽略不计。

如表 1所示，如果单就对客户端和服务器的两个向量C和S进行讨论，则文献^[2]构造的方案计算复杂度和通信复杂度均可以达到O(C_T^t)，文献^[4]中构造的方案其计算复杂度和通信复杂度均大于本文方案的O(T)线性复杂度，因而本文方案具有高效性。

3.3 性能分析

文献^[10]构造了半诚实模型下隐私集合交集协议，本文方案在此基础上设计了模糊匹配方案，并将此方案应用于社交网络中兴趣度的匹配。其不同之处如表 2所示。

在具体分析方案的性能时，用时间来衡量运行的效率。假设该方案在两台处理器为Intel Core2 1.83GHz 32位的计算机上运行，两者之间通过1000M Ethernet相连^[20]。哈希函数采用SHA-1，公钥加密采用256bit的椭圆曲线算法GF(p)，以此来估算出本文方案运行的时间量。其运行环境为Windows Vista Intel Core2 1.83GHz 32bit mode，Time Cycles为1/1.83s，采用SHA-算法(11.4时间周期/字节)，ECIES over GF(p) 256bit。 每次操作运算用时为10^-6s， 加密用时5.65s， 解密用时3.98s。

本文方案运行的时间主要由计算复杂度和通信复杂度决定，因此在不考虑其他时间因素时，其时间T主要包括运算时间和通信时间，其运算时间为： T_comp=(2k·n+2m+k·n)t_hash+(2t_Encryption+t_Decryption)λ ，通信时间为： T_comm=2λ·m/1000， 因此总时间T=T_comp+T_comm。

通过估算得出的数据如表 3所示。从表 3中可以看出，方案的执行时间随着安全参数λ和集合元素个数n的增加而增加；当λ一定时，执行时间基本上随着n增加呈线性增长，与理论分析结果吻合。

图 4可以很好表示出不同n与不同λ所对应的方案执行时间，表明本文方案在大数据环境下也有一定的应用潜力。 如表 4所示，与文献^[10]方案相比，本文方案时间大约只有它的一半。其原因是本文方案的执行时间只包含了运算时间和通信时间，没有将其他因素如程序的运行等考虑进去，因此在真实情况下，两者的性能应该大致相同。

4 结语

本文使用Bloom Filters实现了对两个数据集合的求交集运算：其中一方可以直接得出两个数据集合交集的元素个数，由此判断数据集合之间是否匹配；另一方不能得出交集和交集个数，保证了双方在信息通信过程中的隐私安全。经过理论分析，本文案在计算复杂度和通信复杂度上较其他方案有所改进，达到线性水平，能够较好地应用于社交网络之中。由于本文方案基于半诚实模型情况下，所以不能完全抵御恶意模型下攻击者对数据集合的攻击。