0 引言

近年来，数据呈现出爆炸式增长的趋势，数据量和数据种类变得越来越复杂，大量个人的敏感信息不可避免地充斥在网络中，引发了很多信息泄露事件。目前，隐私保护问题相继受到各个国家、地区的高度重视，以美国、欧盟为首的国家、组织还颁布了相应的法律条款并成立了相关组织来监管数据的传播和使用。

隐私集合交集(Private Set Intersection, PSI)协议是一种涉及到双方(客户端和服务器)数据交互的密码协议^[1-3]，双方共同参与计算出输入数据集合的交集，然而只有客户端一方得到交集的结果，且得不到交集以外的任何数据，服务器不能得到任何数据。隐私集合交集协议具有广泛的应用场景，如隐私数据挖掘^[4]、人类基因研究^[5]、社交网络^[6]、刑事侦察^[7]等各个领域。

2004年，Freedman等^[1]首次提出了隐私集合交集协议问题，分别构造了基于标准模型下的半诚实环境适用协议和基于随机预言机模型的恶意环境适用协议。2005年，Kissner等^[8]提出了多方集合协议。Dachman-Soled等^[9]和Hazay等^[10]提出在恶意敌手攻击模型下效率更高的协议。De Cristofaro^[11]等提出了一个具有线性复杂度授权的PSI协议(Authorized PSI, APSI)。Ateniese等^[12]提出了能够隐藏客户端输入集合大小的PSI协议。Dong等^[13]提出了一种支持大数据、高效的PSI算法，构造了分别基于半诚实模型和恶意模型的协议。Debnath等^[14]构造了标准模型下能够抵抗恶意用户的mPSI(mutual PSI)协议，其具有线性的计算复杂度和通信复杂度。Abadi等^[15]设计了基于分值的外包可委托的O-PSI(Outsourced PSI)协议，它允许多个客户端独立地给服务器上传隐私数据集合，并且能够要求服务器计算出交集。本文分析了文献[13]针对恶意模型下的隐私集合交集协议，发现其存在安全隐患和漏洞，引入了密钥协商协议和分组加密算法进行了改进，提高了协议的效率，并且能够抵抗恶意攻击。

1 预备知识 1.1 双线性配对

令 G₁与G₂分别是由P与Q生成的阶为q的循环加法群，G_T是阶为q的循环乘法群。如果满足以下条件，则称映射e:G₁×G₂→G_T为双线性对^[17]。

1) 双线性性：∀a, b∈Z_q^*，e(aP, bQ)=e(P, Q)^ab；

2) 非退化性：e(P, Q)≠1；

3) 可计算性：存在有效算法计算e(P, Q)。

群G₁、G₂、G_T中的离散对数问题(Discrete Logarithm Problem, DLP)是困难问题，其问题描述为：给定两个元素P∈G₁、Q∈G₂，不可能在多项式时间内找到整数a∈Z_q^*使得Q=aP成立。

1.2 基于身份的密钥交换协议

基于身份的密钥交换协议^[18]分为系统建立和认证密钥协商阶段。协议参与者共同组成集合 D，每个参与者拥有唯一身份标识符ID。密钥生成中心(Key Generation Center, KGC)用来向用户创建和传输密钥。假定Alice与Bob需要交换密钥，那么协议描述如下：

系统建立阶段  双线性映射$ \hat e$:G₁×G₁→G₂，其中：G₁是素数q阶加法群，G₂是素数q阶乘法群，P为G₁生成元。

1) KGC随机选取整数s∈Z_q^*作为私钥，选取哈希函数H₁:{0, 1}^*→G₁^*。

2) KGC计算用户的公钥Q_ID=H₁(ID)和相应的私钥S_ID=sQ_ID，其中ID为用户的身份。

3) KGC在安全信道下将S_ID发送给具有身份信息ID的用户，用户在基于身份的协议中的公私钥对为(Q_ID, S_ID)，其中Q_ID, S_ID∈G₁。

认证密钥协商阶段  用户Alice的公私钥为(Q_A, S_A)，用户Bob的公私钥对为(Q_B, S_B)。

1) Alice和Bob随机选择私钥a, b∈Z_q^*，计算出相应的公钥T_A=aP和T_B=bP。

2) Alice向Bob发送T_A，Bob向Alice发送T_B。

3) Alice计算出会话密钥K_AB=H(A, B, K_A, V_A)，其中:K_A=a·T_B，V_A= $\hat e $(S_A, Q_B)。Bob同样计算出K_BA=H(A, B, K_B, V_B)，其中:K_B=b·T_A，V_B= $\hat e $(S_B, Q_A)。

显然，K_AB=K_BA=H(A, B, abQ, $\hat e $(Q_A, Q_B)^s)，Alice与Bob得到相同的共享密钥K。

此协议的安全性依赖于椭圆曲线上的离散对数困难问题(DLP)以及Diffie-Hellman假设困难问题。

1.3 不经意传输协议

不经意传输协议^[19]是一种保护隐私的双方通信密码协议。发送方以一种保护双方信息安全的方式将输入的一部分内容发送给接收方，发送方并不知道接收方接收的是哪份消息，接收方也不会泄露发送方发送的其他部分。不经意传输协议可以表示为 OT_l^m，即发送方拥有m对l 比特串(x_{j, 0}, x_{j, 1})(0≤j≤m－1)，接收方拥有m比特的选择串r=(r₀, r₁, …, r_m－1)。当r_i为0时，选择x_{j, r0}，否则选择x_{j, r1}。

不经意传输协议OT_l^m的安全性依赖于计算性Diffie-Hellman(Computational Diffie-Hellman, CDH)假设困难问题，其定义如下：

定义1  在x, y∈Z_q^*未知情况下，给定g^x, g^y∈G，求解g^xy。设在时间t内，敌手A成功输出g^xy的概率为：succ_G^CDH(A)=pr[A(g^x, g^y)=g^xy]≤ε，其中ε是可忽略的。如果ε可忽略不计，则CDH问题是(t, ε)困难。

1.4 Bloom过滤器

Bloom Filter^[20]是一种存储数据的结构，支持数据存储和成员查询，实现了 m比特的数组来表示最多有n个元素的集合S={s₁, s₂, …, s_n}。每个Bloom Filter具有k个均匀分布的哈希函数H={h₀, h₁, …, h_k－1}，其映射的值域为[0, m－1]。本文用BF_S来表示元素集合S生成的Bloom Filter，用BF_S[i]来表示BF_S中第i个数据位，用GBF_S来表示元素集合S生成的Garbled Bloom Filter，用GBF_S[i]来表示GBF_S中第i个λ 比特串。如图 1所示，初始化时，所有的数据位都被置为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中。Bloom Filter中一个特定的位置设置为1的概率为p=1－(1－1/m)^kn，文献[17]证明了BF_S漏警率(false positive probability，即x不在集合S中，但是BF_S[h_i(x)]都是1) 的上限值为：

$ \varepsilon = {p^k} \times \left( {1 + O\left( {\frac{k}{p}\sqrt {\frac{{\ln m-k\ln p}}{m}} } \right)} \right) $

其中p=1－(1－1/m)^kn，ε值是可以忽略的。

1.5 秘密共享

秘密共享是一个基本的密码学原语， (t, n)秘密共享方案^[21]就是使用者将秘密s分成n份并设置门限值t，对方得到其中t份以上份额便能有效地恢复出秘密s。当t=n时，通过简单的异或操作就可以得到一个高效的(n, n)秘密共享方案^[22]。其原理是使用者生成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.6 恶意模型

隐私集合交集协议的安全性可以通过与理想模型的对比来进行评价。理想模型中，客户端与服务器将输入提交给可信第三方，由可信第三方来获得交集输出结果。恶意敌手的行为很随意，它可能会想出任何办法来推导秘密信息，也可能在任何时候发送伪造、欺骗信息，与其他(恶意)方合谋进行攻击。

恶意模型^[23]中，没有任何方法会强迫参与方参与协议或者停止协议。客户端与服务器都可能腐化成为恶意参与方或者恶意敌手，它们会产生任意输入或者修改他们的输入，这些输入可能会与正确的输入不同，然后通过输出来获取更多信息。

2 可抵抗恶意攻击的隐私集合交集协议 2.1 原始方案回顾

文献[13]构造的隐私集合交集协议中，用 C和S分别表示客户端和服务器的隐私集合。对于客户端C来说，其按照上述方法生成BF_C。对于服务器S来说，其生成算法如算法1(GBF_S(S, n, m, k, H, λ))所示，算法示例如图 2所示。比如说，令m=15，k=3，当插入元素x₁时，x₁被哈希函数H作用后得到1、3、6，于是x₁被分为s₁¹、s₁²、s₁³，分别存放在相应位置; 当插入元素x₂时，x₂被哈希函数H作用后得到3、9、12，然而GBF_S^[3]已经被x₁的份额占据，于是保持该位置值不变，利用s₁²生成s₂¹、s₂²，使得x₂=s₂¹⊕s₂²⊕s₁²; 同理，当插入x₃时，也按照上述方法解决。当所有元素都已经存放完毕时，则对Garbled Bloom Filter进行遍历，如果存在空位，则随机产生λ比特串填充。

算法1    GBF_S(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[i]=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

      GBFs[j]←{0, 1}^λ；      //随机生成λ比特串

      finalShare=finalShare⊕GBF_S[j]；

    end

    else

       finalShare=finalShare⊕GBFs[j]；

    end

  end

  GBF_S[emptySlot]=finalShare；

end

for i=0 to m-1 do

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

    GBF_S[i]←{0, 1}^λ；      //λ比特串

  end

end

现简要介绍文献[13]中恶意模型下隐私集合交集协议。

1) 协议输入： 服务器集合S，客户端集合C，安全参数λ，集合元素个数n，哈希函数H个数k=λ，BF及GBF大小m，H={m₀, m₁, …, m_k}，安全分组加密算法E。

2) 协议执行：

a)客户端运行算法生成BF_C，然后生成m个λ随机比特串r₀, r₁, …, r_m，并将其发送给服务器。

b)服务器生成GBF_S，并为分组加密算法随机生成密钥sk，计算出c_i=E(sk, r_i‖GBF_S[i])(0≤i≤m－1)，利用(m/2, m)秘密分享方案将sk分成m份(t₀, t₁, …, t_m－1)。

c)服务器与客户端共同参与可抵抗恶意参与方的不经意传输协议OT，客户端使用BF_C作为选择串，如果BF_C[i]=1，客户端接收c_i；如果BF_C[i]=0，客户端接收t_i。

d)客户端通过接收的t_i恢复出密钥sk。客户端创建一个m大小的GBF_C∩S，如果BF_C[i]=0，则GBF_C∩S[i]←{0, 1}^λ；如果BF_C[i]=1，客户端解密c_i得到d_i=E^－1(sk, c_i)，检验起始λ比特串是否等于r_i。如果相等则跳过起始λ比特串，并将第二个λ比特串复制给GBF_C∩S[i]，否则输出⊥并停止协议。最后，客户端用C询问GBF_C∩S并输出C∩S。

为了抵抗恶意用户攻击，客户端向服务器发送m个随机生成λ比特串r₀, r₁, …, r_m。服务器随机生成密钥sk用于分组密码加密Enc，同时计算出c_i=Enc(sk, r_i‖GBF_S[i])，再利用(m/2, m)秘密共享方案将密钥sk分成m份t₀, t₁, …, t_m－1。客户端与服务器共同参与OT协议，当BF_C=0时，服务器接收到t_i；当BF_C=1时，服务器接收到c_i。因此，服务器最终接收到两个数据集合C=c₁, c₂, …, c_α和T=t₁, t₂, …, t_β，且α+β=m，当且仅当β≥m/2时，客户端才能够恢复密钥sk，解密得到r_i‖GBF_S[i]，同时验证其前λ比特是否与r_i相同，如果相同，则GBF_C∩S[i]=GBF_S[i]。

原始方案虽然运用了分组密码和数据串验证两种手段来解决数据的安全问题和加解密数据的认证问题，但是仍然不安全。如果恶意的客户端将BF_C[i]全部设置为1，则可以全部得到c_i；如果将BF_C[i]全部设置为0或者设置m/2以上1的个数，则可以得到t₁, t₂, …, t_β(β≥m/2)，即能够恢复出密钥sk。那么恶意客户端很容易解密所有c_i，便可以得到GBF_S中的所有数据。

2.2 基于密钥交换协议的改进方案

2.1节原始方案中，服务器 S之所以能够泄露出GBF_S中的所有数据，是因为恶意客户端用户将分组密码密钥sk恢复了出来。因此，本文采用密钥协商协议，服务器将分组密钥sk秘密传输给客户端。恶意用户如果没有与服务器密钥交换的过程，即使通过将BF_C[i]全部设置为1的方式得到Enc_sk(GBF_S)，也很难破解得到sk解密密文。为了防止恶意用户篡改GBF_S，本文对GBF_S(S, n, m, k, H, λ)算法进行了改进，使服务器在建立GBF_S的过程中携带具有验证数据正确性的哈希值，得到GBF-M(S, n, m, k, H, λ)生成算法， 其算法描述如下：

算法2    GBF-M(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，GBF-M。

for i=0 to m-1 do

  GBF_S[i]=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[j]←{0, 1}^λ；      //随机生成λ比特串

      finalShare=finalShare⊕GBF_S[j]；

    end

    else

       finalShare=finalShare⊕GBFs[j]；

    end

  end

  GBF_S[emptySlot]=finalShare；

end

for i=0 to m-1 do

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

    GBFS[i]←{0, 1}^λ；      //λ比特串

   end

end

GBF-M=GBF_S‖hash(GBF_S)      //合成新的GBF-M

GBF-M(S, n, m, k, H, λ)生成算法过程可以描述为：

1) 参数建立。客户端C建立BF_C，服务器建立GBF_S并获取GBF-M。设置集合大小m，元素个数n，安全参数λ，哈希函数H={h₀, h₁, …, h_k－1}，分组加解密算法Enc和Dec。

2) 密钥协商。密钥协商之前，客户端会向服务器发送包含身份ID的请求，试图获得对服务器的访问权限。服务器验证客户端的身份后，如果服务器同意，那么客户端与服务器参与基于身份的密钥协商协议，双方共同得到分组加密的共享密钥sk。否则服务器拒绝客户端的请求，协议终止。

3) 数据传输。服务器首先对GBF_S作哈希运算得到hash(GBF_S)，并与GBF-M提取出的hash(GBF_S)进行对比，如果相同则继续对GBF_S[i]进行哈希运算，即hash(GBF_S[i])，产生t比特输出，然后用密钥sk对GBF_S[i]和hash(GBF_S[i])分组加密得到E_i=Enc_sk(GBF_S[i]‖hash(GBF_S[i]))，否则协议停止。服务器与客户端共同参与OT协议，服务器作为发送方将m对(λ+t)比特串(x_{i, 0}, x_{i, 1})发送给客户端(x_{i, 0}是随机生成的(λ+t)比特串，0≤i≤1)。如果BF_C[i]=0，客户端则接收随机(λ+t)比特串；如果BF_C[i]=1，客户端则接收E_i=Enc_sk(GBF_S[i]‖hash(GBF_S[i]))。

4) 计算交集。客户端建立空白GBF_C∩S，如果BF_C[i]=0，则GBF_C∩S[i]←r{0, 1}^λ；如果BF_C[i]=1，则客户端解密E_i，即Dec_sk(Enc_sk(GBF_S[i]‖hash(GBF_S[i])))得到GBF_S[i]和哈希值hash(GBF_S[i])。然后，客户端对GBF_S[i]哈希并与hash(GBF_S[i])进行比对。如果两个哈希值相同，则使得GBF_C∩S[i]=GBF_S[i]，否则该过程失败。最终客户端可以用C对GBF_C∩S进行查询，得到两个集合的交集。

值得注意的是，改进的GBF_S生成算法中，合成的GBF-M由GBF_S和hash(GBF_S)两部分组成，“‖”表示的是将Garble Bloom Filter中m个λ比特串联接起来。

3 方案分析 3.1 安全性分析

本文方案的安全性依赖于基于身份的密钥协商协议的安全性，以及不经意传输协议的安全性。下面对该方案的安全性进行分析。

定理1   设 C、S分别是客户端与服务器的两个集合，C∩S是两个集合的交集，f_∩是本文提出生成交集C∩S的PSI协议。如果DLP与CDH是数学困难问题，那么密钥协商协议和不经意传输协议OT是安全的，该方案能够在恶意客户端用户存在的条件下安全得计算出C∩S，即：

f_∩(C, S)=(f_C(C, S), f_S(C, S))=(C∩S, ∧)。

证明  如果OT_λ^m是安全的，则发送者和接收者的模拟器存在。从客户端的角度来看，本文构造了一个模拟器Sim_C来接收客户端的输入与输出。假设存在恶意用户敌手A，模拟器Sim_C调用敌手A向随机预言机进行询问，从询问中提取出C′。Sim_C建立集合C″，将C″发送给服务器S，获得C″∩S并构造出GBF_C″∩S。然后，Sim_C调用OT模拟器Sim_C^OT，参与不经意传输协议OT。

显然，C″∩S是正确的交集，r^C是Sim_C选择的随机投掷的硬币值，它具有随机的特性，那么Sim_C输出的视图为(C′, r^C, Sim_C^OT(GBF_C′∩S ))。密钥交换过程中，敌手A不能获取到分组密钥sk，即不能对GBF_C″∩S进行解密。从本文方案的视图来看，它包括集合C′、r^C以及OT协议传送过程中的任何消息。从模拟的视图来看，集合C′与方案中的集合C完全一样。Sim_C输出的r^C是随机产生的，两个随机硬币值的分布是完全一样的。因为OT协议是安全的，方案的视图与Sim_C^OT(GBF_C′∩S )的视图同样也是均匀分布的。所以说这两个视图不可区分。

同理，从服务器角度来看，本文构造了一个模拟器Sim_S来接收服务器的输入与输出。Sim_S选择随机硬币值r^S′，建立集合S′并生成GBF_S′，同时Sim_S调用OT模拟器Sim_S^OT，参与不经意传输协议OT，那么Sim_S输出的视图为(S′, r^S′, Sim_S^OT(GBF_S′, ∧))。从本文方案的视图来看，它包括集合S′、r^S′以及OT协议传送过程中的任何消息。从模拟的视图来看，集合S′与方案中的集合S完全一样。Sim_S输出的r^S′是随机产生的，两个随机硬币值的分布是完全一样的。OT协议是安全的，方案的视图与Sim_S^OT(GBF_S′, ∧)的视图同样也是均匀分布的。所以说这两个视图不可区分。

综上所述，本文方案具有抵抗恶意攻击的安全性。

定理2   协议执行过程中，假设安全的客户端C严格按照协议得到了分组密码密钥sk，那么C可以根据BF_C的{0, 1}取值得到GBF_C∩S。但是C仍可以利用BF_C得到除C∩S以外的服务器S的数据内容，用A表示此事件，则其概率为：

$ P\left( A \right) \le \varepsilon = {p^k} \times \left( {1 + O\left( {\frac{k}{p}\sqrt {\frac{{\ln m-k\ln p}}{m}} } \right)} \right) $

而ε是可以忽略的，因此C不能得到除C∩S以外的服务器S的内容，所以协议是安全的。

证明  对于0≤i≤k－1，用a_i表示事件GBF_C∩S[h_i(x)]等于x的第i秘密份额。如果∀x∈C∩S，则p[a₀∧a₁∧…∧a_k－1]=1，即x为C与S的交集元素时，C完全能够将x计算出来。如果∀x∉C∩S但x∈S－C∩S，即x不是C与S的交集元素却是S的元素时，C有可能利用BF_C将x的所有秘密份额从GBF_S复制到GBF_C∩S中。由于x被哈希后映射到的Bloom Filter位置被设置为1，那么C就有可能将x秘密恢复出来，其概率与生成BF时的漏警率(false positive probability)的上限ε等价，于是P(A)≤ε，ε可以忽略不计，说明C即使在得到GBF_S或GBF_C∩S 的情况下，几乎不可能将交集以外的元素恢复出来。

如表 1所示，将本文方案与文献[1, 10, 13]方案进行了安全性对比。本文方案基于随机预言机模型，能够抵抗恶意敌手攻击。与文献[13]中提出的用于恶意模型的方案相比较，本文方案基于的安全假设困难性更高，更具有安全性。一方面，恶意攻击者不能获取到合法客户端与服务器的数据元素；另一方面，合法客户端用户也不能获得服务器除交集以外的元素，增强了安全防御与隐私保护功能。

3.2 效率分析

如表 2所示，将本文方案与文献[1, 10, 13]方案的效率进行了比较分析，其中 w和v分别代表客户端集合C与服务器集合S 中的元素个数。本文方案与文献[1]方案相比，两者的通信复杂度相同，但是计算复杂度上本文方案有较大优势。本文方案与文献[10]方案相比，尽管两者的通信复杂度和计算复杂度均为线性，但是本文方案中对 GBF 操作采用的是分组加密，而文献[10]方案对 BF 操作采用的是公钥加密，因此本文方案在效率上较文献[10]方案要高。与文献[13]方案相比，本文方案中客户端与服务器在构造 BF_C和GBF_S，以及双方参与OT协议客户端获得交集的过程中，两者的计算复杂度和通信复杂度基本相同，但较文献[13]方案有所减少：

1) 文献[13]方案中客户端为了获取密钥sk，是通过秘密共享的方式进行恢复获取，而本文方案的sk是通过密钥协商的方式提前获得，减少了密钥拆分和恢复的运算量。

2) 原有方案为了验证解密数据的正确性，客户端事先发送给服务器一些随机比特串，服务器接收比特串后，将其与GBF_S一起加密发送给客户端，客户端需要比对比特串，从而达到完整性与正确性验证的目的。而本文方案是直接对GBF_S和对GBF_S 的哈希值进行加密，降低了加解密数据量。

4 结语

本文针对当前备受关注的隐私保护问题^[24]，结合隐私集合交集协议，分析了文献[13]所提协议所存在的安全问题，并引入了密钥协商协议和哈希算法对其进行了改进，保证了分组加密密钥的安全性，并且针对协议的安全性和复杂度，与经典的隐私交集协议进行了分析对比。分析结果表明本文方案能够抵抗非法用户的恶意攻击，确保了双方隐私的安全。综合分析表明，该协议较其他相关同类协议效率更高，能够灵活高效地应用于隐私保护场景中。