一类可抵抗恶意攻击的隐私集合交集协议

罗小双，杨晓元，王绪安

(1.武警工程大学 电子技术系，西安710086； 2.网络与信息安全武警部队重点实验室,西安 710086)

一类可抵抗恶意攻击的隐私集合交集协议

罗小双1,2，杨晓元1,2*，王绪安1,2

(1.武警工程大学 电子技术系，西安710086； 2.网络与信息安全武警部队重点实验室,西安 710086)

(*通信作者电子邮箱xyyangwj@126.com)

针对安全两方计算中隐私集合交集计算问题，提出了一种改进的基于BloomFilter数据结构的隐私集合交集协议。该协议能够保证双方在各自隐私安全的前提下，计算出两者数据集合的交集，其中只有一方能够计算出交集元素，另外一方无法计算得到交集，并且双方都不能获得或推测出对方除交集以外的任何集合元素，确保了参与双方敏感信息的安全保密。所提协议引入了基于身份的密钥协商协议，能够抵抗非法用户的恶意攻击，达到隐私保护和安全防御的目的，抵御了密钥泄露的风险，减少了加解密的运算量，并且具备支持较大规模集合数据的运算能力。

隐私保护；隐私集合交集；不经意传输；秘密共享；密钥协商

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 双线性配对

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

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

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

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

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

2)KGC计算用户的公钥QID=H1(ID)和相应的私钥SID=sQID，其中ID为用户的身份。

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

认证密钥协商阶段 用户Alice的公私钥为(QA,SA)，用户Bob的公私钥对为(QB,SB)。

2)Alice向Bob发送TA，Bob向Alice发送TB。

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

1.3 不经意传输协议

1.4Bloom过滤器

BloomFilter[20]是一种存储数据的结构，支持数据存储和成员查询，实现了m比特的数组来表示最多有n个元素的集合S={s1,s2,…,sn}。每个Bloom Filter具有k个均匀分布的哈希函数H={h0,h1,…,hk-1}，其映射的值域为[0,m-1]。本文用BFS来表示元素集合S生成的Bloom Filter，用BFS[i]来表示BFS中第i个数据位，用GBFS来表示元素集合S生成的Garbled Bloom Filter，用GBFS[i]来表示GBFS中第i个λ比特串。如图1所示，初始化时，所有的数据位都被置为0，当插入元素x∈S时，k个哈希函数对x进行运算得到k个索引数，令相应位置为1，即BFS[hi(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]证明了BFS漏警率(false positive probability，即x不在集合S中，但是BFS[hi(x)]都是1)的上限值为：

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

图1 用Bloom Filter存放x示意图

1.5 秘密共享

秘密共享是一个基本的密码学原语，(t,n)秘密共享方案[21]就是使用者将秘密s分成n份并设置门限值t，对方得到其中t份以上份额便能有效地恢复出秘密s。当t=n时，通过简单的异或操作就可以得到一个高效的(n,n)秘密共享方案[22]。其原理是使用者生成n-1个与s相同长度的随机比特串r1,r2,…,rn-1，计算出rn=r1⊕r2⊕…⊕rn-1⊕s，每个ri都是秘密的组成份额，通过计算r1⊕r2⊕…⊕rn便能够恢复出秘密s，并且少于n份额的信息时不会泄露任何秘密。

1.6 恶意模型

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

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

2 可抵抗恶意攻击的隐私集合交集协议

2.1 原始方案回顾

图2 GBFS(S,n,m,k,H,λ)算法示例

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

输入 数据集合S，集合元素个数n，Bloom Filter位置个数m,哈希函数个数k,H={h0,h1,…,hk-1},安全参数λ；

输出 An(m,n,k,H,λ)-Garbled Bloom FilterGBFS，GBFS=newm-element array of bit strings。

fori=0 tom-1 doGBFS[i]=NULL；

//将m个位置赋空值

end

for eachx∈Sdo

//插入xemptySlot=-1,finalShare=x； fori=0 tok-1 doj=hi(x)；

//将x哈希为k个索引值 ifemptySlot==-1 thenemptySlot=j;

elseGBFs[j]←{0,1}λ；

//随机生成λ比特串finalShare=finalShare⊕GBFS[j]；

end

elsefinalShare=finalShare⊕GBFs[j]；

end

end

GBFS[emptySlot]=finalShare；

end

fori=0 tom-1 do ifGBFS[i]=NULL then

//遍历后空位随机填补GBFS[i]←{0,1}λ；

//λ比特串

end

end

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

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

2)协议执行：

a)客户端运行算法生成BFC，然后生成m个λ随机比特串r0,r1,…,rm，并将其发送给服务器。

b)服务器生成GBFS，并为分组加密算法随机生成密钥sk，计算出ci=E(sk,ri‖GBFS[i])(0≤i≤m-1)，利用(m/2,m)秘密分享方案将sk分成m份(t0,t1,…,tm-1)。

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

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

为了抵抗恶意用户攻击，客户端向服务器发送m个随机生成λ比特串r0,r1,…,rm。服务器随机生成密钥sk用于分组密码加密Enc，同时计算出ci=Enc(sk,ri‖GBFS[i])，再利用(m/2,m)秘密共享方案将密钥sk分成m份t0,t1,…,tm-1。客户端与服务器共同参与OT协议，当BFC=0时，服务器接收到ti；当BFC=1时，服务器接收到ci。因此，服务器最终接收到两个数据集合C=c1,c2,…,cα和T=t1,t2,…,tβ，且α+β=m，当且仅当β≥m/2时，客户端才能够恢复密钥sk，解密得到ri‖GBFS[i]，同时验证其前λ比特是否与ri相同，如果相同，则GBFC∩S[i]=GBFS[i]。

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

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

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

算法2GBF-M(S,n,m,k,H,λ)生成算法。

输入 数据集合S，集合元素个数n，Bloom Filter位置个数m,哈希函数个数k,H={h0,h1,…,hk-1},安全参数λ；

输出 An(m,n,k,H,λ)-Garbled Bloom FilterGBFS，GBFS=newm-element array of bit strings，GBF-M。

fori=0 tom-1 doGBFS[i]=NULL；

//将m个位置赋空值

end

for eachx∈Sdo

//插入xemptySlot=-1,finalShare=x； fori=0 tok-1 doj=hi(x)；

//将x哈希为k个索引值 ifemptySlot==-1 thenemptySlot=j;

elseGBFS[j]←{0,1}λ；

//随机生成λ比特串finalShare=finalShare⊕GBFS[j]；

end

elsefinalShare=finalShare⊕GBFs[j]；

end

end

GBFS[emptySlot]=finalShare；

end

fori=0 tom-1 do ifGBFS[i]=NULL then

//遍历后空位随机填补GBFS[i]←{0,1}λ；

//λ比特串

end

end

GBF-M=GBFS‖hash(GBFS)

//合成新的GBF-M

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

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

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

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

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

3 方案分析

3.1 安全性分析

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

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

f∩(C,S)=(fC(C,S),fS(C,S))=(C∩S,∧)。

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

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

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

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

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

表1 不同方案安全性对比

3.2 效率分析

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

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

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

表2 不同方案复杂度对比

4 结语

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

)

[1]FREEDMMJ,NISSIMK,PINKASB.Efficientprivatematchingandsetintersection[C] //Proceedingsofthe2004InternationalConferenceontheTheoryandApplicationsofCryptographicTechniques,LNCS3027.Berlin:Springer, 2004: 1-19.

[2] 孙茂华,宫哲.一种保护隐私集合并集外包计算协议[J].密码学报,2016,3(2):114-125.(SUNMH,GONGZ.Aprivacy-preservingoutsourcingsetunionprotocol[J].JournalofCryptologicResearch, 2016, 3(2): 114-125.)

[3] 朱国斌,谭元巍,赵洋,等.高效的安全几何交集计算协议[J].电子科技大学学报,2014,43(5):781-786.(ZHUGB,TANYW,ZHAOY,etal.Anefficientandsecuregeometricintersectioncomputationprotocol[J].JournalofUniversityofElectronicScienceandTechnologyofChina, 2014, 43(5): 781-786.)

[4]AGGARWALCC,YUPS.Privacy-preservingdatamining:modelsandalgorithms[M]//AdvancesinDatabaseSystems34.NewYork:SpringerUS, 2008: 11-52.

[5]BALDIP,BARONIOR,DECRISTOFAROE,etal.CounteringGATTACA:efficientandsecuretestingoffully-sequencedhumangenomes[C]//CCS’11:Proceedingsofthe18thACMConferenceonComputerandCommunicationsSecurity.NewYork:ACM, 2011: 691-702.

[6]MEZZOURG,PERRIGA,GLIGORV,etal.Privacy-preservingrelationshippathdiscoveryinsocialnetworks[C] //CANS2009:Proceedingsofthe2009InternationalConferenceonCryptologyandNetworkSecurity,LNCS5888.Berlin:Springer, 2009: 189-208.

[7]NAGARAJAS,MITTALP,HONGCY,etal.BotGrep:findingP2Pbotswithstructuredgraphanalysis[C]//Proceedingsofthe19thUSENIXConferenceonSecurity.Berkeley,CA:USENIXAssociation, 2010: 7-7.

[8]KISSNERL,SONGD.Privacy-preservingsetoperations[C]//CRYPTO’05:Proceedingsofthe25thAnnualInternationalConferenceonAdvancesinCryptology,LNCS3621.Berlin:Springer, 2005: 241-257.

[9]DACHMAN-SOLEDD,MALKINT,RAYKOVAM,etal.Efficientrobustprivatesetintersection[C]//Proceedingsofthe2009InternationalConferenceonAppliedCryptographyandNetworkSecurity,LNCS5536.Berlin:Springer, 2009: 125-142.

[10]HAZAYC,NISSIMK.Efficientsetoperationsinthepresenceofmaliciousadversaries[C]//PKC’10:Proceedingsofthe13thInternationalConferenceonPracticeandTheoryinPublicKeyCryptography.Berlin:Springer, 2010: 312-331.

[11]DECRISTOFAROE,TSUDIKG.Practicalprivatesetintersectionprotocolswithlinearcomplexity[C]//Proceedingsofthe2010InternationalConferenceonFinancialCryptographyandDataSecurity,LNCS6052.Berlin:Springer, 2010: 143-159.

[12]ATENIESEG,DECRISTOFAROE,TSUDIKG. (If)sizematters:Size-hidingprivatesetintersection[C]//PKC2011:Proceedingsofthe14thInternationalConferenceonPracticeandTheoryinPublicKeyCryptography,LNCS6571.Berlin:Springer, 2011: 156-173.

[13]DONGCY,CHENLQ,WENZK.Whenprivatesetintersectionmeetsbigdata:anefficientandscalableprotocol[C]//CCS’13:Proceedingsofthe2013ACMSIGSACconferenceonComputer&communicationssecurity.NewYork:ACM, 2013: 789-800.

[14]DEBNATHSK,DUTTAR.Afairandefficientmutualprivatesetintersectionprotocolfromatwo-wayobliviouspseudorandomfunction[C]//ICISC2014:Proceedingsofthe17thInternationalConferenceonInformationSecurityandCryptology,LNCS8949.Berlin:Springer, 2014: 343-359.

[15]ABADIA,TERZISS,DONGCY.O-PSI:delegatedprivatesetintersectiononoutsourceddatasets[C]//SEC2015:Proceedingsofthe2015IFIPInternationalInformationSecurityConferenceonICTSystemsSecurityandPrivacyProtection,IFIPAICT455.Berlin:Springer, 2015: 3-17.

[16]RINDALP,ROSULEKM.Improvedprivatesetintersectionagainstmaliciousadversaries[C]//EUROCRYPT2017:Proceedingsofthe36thAnnualInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques,LNCS10210.Berlin:Springer, 235-259.

[17]BONEHD,FRANKLINMK.Identity-basedencryptionfromtheWeilparing[C]//CRYPTO2001:Proceedingsofthe21stAnnualInternationalCryptologyConferenceonAdvancesinCryptology,LNCS2139.Berlin:Springer, 2001: 213-229.

[18]RYUEK,YOONEJ,YOOKY.AnefficientID-basedauthenticatedkeyagreementprotocolfrompairings[C]//Networking2004:Proceedingsofthe2004InternationalConferenceonResearchinNetworking,LNCS3042.Berlin:Springer, 2004: 1458-1463.

[19]RABINMO.Howtoexchangesecretsbyoblivioustransfer,TR-81 [R].Cambridge,MA:HarvardUniversity,AikenComputationLaboratory, 1981.

[20]BLOOMBH.Space/timetrade-offsinhashcodingwithallowableerrors[J].CommunicationsoftheACM, 1970, 13(7): 422-426.

[21]SHAMIRA.Howtoshareasecret[J].CommunicationsoftheACM, 1979, 22(11): 612-613.

[22]SCHNEIERB.AppliedCryptography-Protocols,Algorithms,andSourceCodeinC[M]. 2nded.NewYork:JohnWiley&Sons, 1995: 113-117.

[23]GOLDREICHO.FoundationofCryptography:Volume2,BasicApplications[M].Cambridge,MA:CambridgeUniversityPress, 2009: 620-625.

[24] 冯登国,张敏,李昊.大数据安全与隐私保护[J].计算机学报,2014,37(1):246-258.(FENGDG,ZHANGM,LIH.Bigdatasecurityandprivacyprotection[J].ChineseJournalofComputers, 2014, 37(1): 246-258.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(U1636114, 61572521, 61772472),theNaturalScienceFoundationofShaanxiProvince(2014JM8300, 2014JQ8358, 2015JQ6231, 2016JQ6037).

LUO Xiaoshuang, born in 1992, M. S. candidate. His research interests include information security, cryptology.

YANG Xiaoyuan, born in 1959, M. S., professor. His research interests include information security, cryptology.

WANG Xu’an, born in 1981, Ph. D., associate professor. His research interests include information security, cryptology.

A private set intersection protocol against malicious attack

LUO Xiaoshuang1,2, YANG Xiaoyuan1,2*, WANG Xu’an1,2

(1.DepartmentofElectronicTechnology,EngineeringCollegeoftheArmedPoliceForce,Xi’anShaanxi710086,China; 2.KeyLaboratoryofNetwork&InformationSecurityundertheChineseArmedPoliceForce,Xi’anShaanxi710086,China)

Aiming at the problem of private set intersection calculation in secure two-party computation, an improved private set intersection protocol based on Bloom Filter was proposed. On the premise of ensuring the security of both parties about their own privacy, the intersection of two datasets could be calculated. Only one party can calculate the intersection elements whereas the other party can’t calculate the intersection. Both parties can’t obtain or infer any other set elements except the intersection of the other party, which ensures the security of sensitive information for both parties. The proposed protocol introduced the identity-based key agreement protocol, which can resist the malicious attacks of illegal users, protect the privacy and achieve the security defense, resist the risk of key disclosure, reduce the amount of encryption and decryption. The proposed protocol has the ability to support large scale data computation.

privacy preserving; Private Set Intersection (PSI); oblivious transfer; secret sharing; key agreement

2016- 12- 06;

2017- 02- 09。 基金项目:国家自然科学基金资助项目(U1636114,61572521,61402531)；陕西省自然科学基金资助项目(2014JM8300,2014JQ8358,2015JQ6231,2016JQ6037)。

罗小双(1992—),男，陕西安康人，硕士研究生，CCF会员，主要研究方向:信息安全、密码学； 杨晓元(1959—)，男，湖南湘潭人，教授，硕士，主要研究方向：信息安全、密码学； 王绪安(1981—)，男，湖北公安人，副教授，博士，主要研究方向：信息安全、密码学。

1001- 9081(2017)06- 1593- 06

10.11772/j.issn.1001- 9081.2017.06.1593

TP

A