羅小雙，楊曉元，王緒安

(1.武警工程大學(xué) 電子技術(shù)系，西安710086； 2.網(wǎng)絡(luò)與信息安全武警部隊重點實驗室,西安 710086)

一類可抵抗惡意攻擊的隱私集合交集協(xié)議

羅小雙1,2，楊曉元1,2*，王緒安1,2

(1.武警工程大學(xué) 電子技術(shù)系，西安710086； 2.網(wǎng)絡(luò)與信息安全武警部隊重點實驗室,西安 710086)

(*通信作者電子郵箱xyyangwj@126.com)

針對安全兩方計算中隱私集合交集計算問題，提出了一種改進的基于BloomFilter數(shù)據(jù)結(jié)構(gòu)的隱私集合交集協(xié)議。該協(xié)議能夠保證雙方在各自隱私安全的前提下，計算出兩者數(shù)據(jù)集合的交集，其中只有一方能夠計算出交集元素，另外一方無法計算得到交集，并且雙方都不能獲得或推測出對方除交集以外的任何集合元素，確保了參與雙方敏感信息的安全保密。所提協(xié)議引入了基于身份的密鑰協(xié)商協(xié)議，能夠抵抗非法用戶的惡意攻擊，達到隱私保護和安全防御的目的，抵御了密鑰泄露的風(fēng)險，減少了加解密的運算量，并且具備支持較大規(guī)模集合數(shù)據(jù)的運算能力。

隱私保護；隱私集合交集；不經(jīng)意傳輸；秘密共享；密鑰協(xié)商

0 引言

近年來，數(shù)據(jù)呈現(xiàn)出爆炸式增長的趨勢，數(shù)據(jù)量和數(shù)據(jù)種類變得越來越復(fù)雜，大量個人的敏感信息不可避免地充斥在網(wǎng)絡(luò)中，引發(fā)了很多信息泄露事件。目前，隱私保護問題相繼受到各個國家、地區(qū)的高度重視，以美國、歐盟為首的國家、組織還頒布了相應(yīng)的法律條款并成立了相關(guān)組織來監(jiān)管數(shù)據(jù)的傳播和使用。

隱私集合交集(Private Set Intersection, PSI)協(xié)議是一種涉及到雙方(客戶端和服務(wù)器)數(shù)據(jù)交互的密碼協(xié)議[1-3]，雙方共同參與計算出輸入數(shù)據(jù)集合的交集，然而只有客戶端一方得到交集的結(jié)果，且得不到交集以外的任何數(shù)據(jù)，服務(wù)器不能得到任何數(shù)據(jù)。隱私集合交集協(xié)議具有廣泛的應(yīng)用場景，如隱私數(shù)據(jù)挖掘[4]、人類基因研究[5]、社交網(wǎng)絡(luò)[6]、刑事偵察[7]等各個領(lǐng)域。

2004年，F(xiàn)reedman等[1]首次提出了隱私集合交集協(xié)議問題，分別構(gòu)造了基于標(biāo)準(zhǔn)模型下的半誠實環(huán)境適用協(xié)議和基于隨機預(yù)言機模型的惡意環(huán)境適用協(xié)議。2005年，Kissner等[8]提出了多方集合協(xié)議。Dachman-Soled等[9]和Hazay等[10]提出在惡意敵手攻擊模型下效率更高的協(xié)議。De Cristofaro[11]等提出了一個具有線性復(fù)雜度授權(quán)的PSI協(xié)議(Authorized PSI, APSI)。Ateniese等[12]提出了能夠隱藏客戶端輸入集合大小的PSI協(xié)議。Dong等[13]提出了一種支持大數(shù)據(jù)、高效的PSI算法，構(gòu)造了分別基于半誠實模型和惡意模型的協(xié)議。Debnath等[14]構(gòu)造了標(biāo)準(zhǔn)模型下能夠抵抗惡意用戶的mPSI(mutual PSI)協(xié)議，其具有線性的計算復(fù)雜度和通信復(fù)雜度。Abadi等[15]設(shè)計了基于分值的外包可委托的O-PSI(Outsourced PSI)協(xié)議，它允許多個客戶端獨立地給服務(wù)器上傳隱私數(shù)據(jù)集合，并且能夠要求服務(wù)器計算出交集。本文分析了文獻[13]針對惡意模型下的隱私集合交集協(xié)議，發(fā)現(xiàn)其存在安全隱患和漏洞，引入了密鑰協(xié)商協(xié)議和分組加密算法進行了改進，提高了協(xié)議的效率，并且能夠抵抗惡意攻擊。

1 預(yù)備知識

1.1 雙線性配對

令G1與G2分別是由P與Q生成的階為q的循環(huán)加法群，GT是階為q的循環(huán)乘法群。如果滿足以下條件，則稱映射e:G1×G2→GT為雙線性對[17]。

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

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

1.2 基于身份的密鑰交換協(xié)議

基于身份的密鑰交換協(xié)議[18]分為系統(tǒng)建立和認證密鑰協(xié)商階段。協(xié)議參與者共同組成集合D，每個參與者擁有唯一身份標(biāo)識符ID。密鑰生成中心(Key Generation Center, KGC)用來向用戶創(chuàng)建和傳輸密鑰。假定Alice與Bob需要交換密鑰，那么協(xié)議描述如下：

2)KGC計算用戶的公鑰QID=H1(ID)和相應(yīng)的私鑰SID=sQID，其中ID為用戶的身份。

3)KGC在安全信道下將SID發(fā)送給具有身份信息ID的用戶，用戶在基于身份的協(xié)議中的公私鑰對為(QID,SID)，其中QID,SID∈G1。

認證密鑰協(xié)商階段 用戶Alice的公私鑰為(QA,SA)，用戶Bob的公私鑰對為(QB,SB)。

2)Alice向Bob發(fā)送TA，Bob向Alice發(fā)送TB。

此協(xié)議的安全性依賴于橢圓曲線上的離散對數(shù)困難問題(DLP)以及Diffie-Hellman假設(shè)困難問題。

1.3 不經(jīng)意傳輸協(xié)議

1.4Bloom過濾器

BloomFilter[20]是一種存儲數(shù)據(jù)的結(jié)構(gòu)，支持數(shù)據(jù)存儲和成員查詢，實現(xiàn)了m比特的數(shù)組來表示最多有n個元素的集合S={s1,s2,…,sn}。每個Bloom Filter具有k個均勻分布的哈希函數(shù)H={h0,h1,…,hk-1}，其映射的值域為[0,m-1]。本文用BFS來表示元素集合S生成的Bloom Filter，用BFS[i]來表示BFS中第i個數(shù)據(jù)位，用GBFS來表示元素集合S生成的Garbled Bloom Filter，用GBFS[i]來表示GBFS中第i個λ比特串。如圖1所示，初始化時，所有的數(shù)據(jù)位都被置為0，當(dāng)插入元素x∈S時，k個哈希函數(shù)對x進行運算得到k個索引數(shù)，令相應(yīng)位置為1，即BFS[hi(x)]=1(0≤i≤k-1)。當(dāng)查詢y是否在S中時，y同樣被k個哈希函數(shù)運算，得到k個哈希值來檢查對應(yīng)的數(shù)據(jù)位，如果其中任何一個數(shù)據(jù)位為0，則y不在集合S中，否則y可能存在于S中。Bloom Filter中一個特定的位置設(shè)置為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 秘密共享

秘密共享是一個基本的密碼學(xué)原語，(t,n)秘密共享方案[21]就是使用者將秘密s分成n份并設(shè)置門限值t，對方得到其中t份以上份額便能有效地恢復(fù)出秘密s。當(dāng)t=n時，通過簡單的異或操作就可以得到一個高效的(n,n)秘密共享方案[22]。其原理是使用者生成n-1個與s相同長度的隨機比特串r1,r2,…,rn-1，計算出rn=r1⊕r2⊕…⊕rn-1⊕s，每個ri都是秘密的組成份額，通過計算r1⊕r2⊕…⊕rn便能夠恢復(fù)出秘密s，并且少于n份額的信息時不會泄露任何秘密。

1.6 惡意模型

隱私集合交集協(xié)議的安全性可以通過與理想模型的對比來進行評價。理想模型中，客戶端與服務(wù)器將輸入提交給可信第三方，由可信第三方來獲得交集輸出結(jié)果。惡意敵手的行為很隨意，它可能會想出任何辦法來推導(dǎo)秘密信息，也可能在任何時候發(fā)送偽造、欺騙信息，與其他(惡意)方合謀進行攻擊。

惡意模型[23]中，沒有任何方法會強迫參與方參與協(xié)議或者停止協(xié)議?？蛻舳伺c服務(wù)器都可能腐化成為惡意參與方或者惡意敵手，它們會產(chǎn)生任意輸入或者修改他們的輸入，這些輸入可能會與正確的輸入不同，然后通過輸出來獲取更多信息。

2 可抵抗惡意攻擊的隱私集合交集協(xié)議

2.1 原始方案回顧

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

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

輸入 數(shù)據(jù)集合S，集合元素個數(shù)n，Bloom Filter位置個數(shù)m,哈希函數(shù)個數(shù)k,H={h0,h1,…,hk-1},安全參數(shù)λ；

輸出 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

現(xiàn)簡要介紹文獻[13]中惡意模型下隱私集合交集協(xié)議。

1)協(xié)議輸入：服務(wù)器集合S，客戶端集合C，安全參數(shù)λ，集合元素個數(shù)n，哈希函數(shù)H個數(shù)k=λ，BF及GBF大小m，H={m0,m1,…,mk}，安全分組加密算法E。

2)協(xié)議執(zhí)行：

a)客戶端運行算法生成BFC，然后生成m個λ隨機比特串r0,r1,…,rm，并將其發(fā)送給服務(wù)器。

b)服務(wù)器生成GBFS，并為分組加密算法隨機生成密鑰sk，計算出ci=E(sk,ri‖GBFS[i])(0≤i≤m-1)，利用(m/2,m)秘密分享方案將sk分成m份(t0,t1,…,tm-1)。

c)服務(wù)器與客戶端共同參與可抵抗惡意參與方的不經(jīng)意傳輸協(xié)議OT，客戶端使用BFC作為選擇串，如果BFC[i]=1，客戶端接收ci；如果BFC[i]=0，客戶端接收ti。

d)客戶端通過接收的ti恢復(fù)出密鑰sk?？蛻舳藙?chuàng)建一個m大小的GBFC∩S，如果BFC[i]=0，則GBFC∩S[i]←{0,1}λ；如果BFC[i]=1，客戶端解密ci得到di=E-1(sk,ci)，檢驗起始λ比特串是否等于ri。如果相等則跳過起始λ比特串，并將第二個λ比特串復(fù)制給GBFC∩S[i]，否則輸出⊥并停止協(xié)議。最后，客戶端用C詢問GBFC∩S并輸出C∩S。

為了抵抗惡意用戶攻擊，客戶端向服務(wù)器發(fā)送m個隨機生成λ比特串r0,r1,…,rm。服務(wù)器隨機生成密鑰sk用于分組密碼加密Enc，同時計算出ci=Enc(sk,ri‖GBFS[i])，再利用(m/2,m)秘密共享方案將密鑰sk分成m份t0,t1,…,tm-1?？蛻舳伺c服務(wù)器共同參與OT協(xié)議，當(dāng)BFC=0時，服務(wù)器接收到ti；當(dāng)BFC=1時，服務(wù)器接收到ci。因此，服務(wù)器最終接收到兩個數(shù)據(jù)集合C=c1,c2,…,cα和T=t1,t2,…,tβ，且α+β=m，當(dāng)且僅當(dāng)β≥m/2時，客戶端才能夠恢復(fù)密鑰sk，解密得到ri‖GBFS[i]，同時驗證其前λ比特是否與ri相同，如果相同，則GBFC∩S[i]=GBFS[i]。

原始方案雖然運用了分組密碼和數(shù)據(jù)串驗證兩種手段來解決數(shù)據(jù)的安全問題和加解密數(shù)據(jù)的認證問題，但是仍然不安全。如果惡意的客戶端將BFC[i]全部設(shè)置為1，則可以全部得到ci；如果將BFC[i]全部設(shè)置為0或者設(shè)置m/2以上1的個數(shù)，則可以得到t1,t2,…,tβ(β≥m/2)，即能夠恢復(fù)出密鑰sk。那么惡意客戶端很容易解密所有ci，便可以得到GBFS中的所有數(shù)據(jù)。

2.2 基于密鑰交換協(xié)議的改進方案

2.1節(jié)原始方案中，服務(wù)器S之所以能夠泄露出GBFS中的所有數(shù)據(jù)，是因為惡意客戶端用戶將分組密碼密鑰sk恢復(fù)了出來。因此，本文采用密鑰協(xié)商協(xié)議，服務(wù)器將分組密鑰sk秘密傳輸給客戶端。惡意用戶如果沒有與服務(wù)器密鑰交換的過程，即使通過將BFC[i]全部設(shè)置為1的方式得到Encsk(GBFS)，也很難破解得到sk解密密文。為了防止惡意用戶篡改GBFS，本文對GBFS(S,n,m,k,H,λ)算法進行了改進，使服務(wù)器在建立GBFS的過程中攜帶具有驗證數(shù)據(jù)正確性的哈希值，得到GBF-M(S,n,m,k,H,λ)生成算法，其算法描述如下：

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

輸入 數(shù)據(jù)集合S，集合元素個數(shù)n，Bloom Filter位置個數(shù)m,哈希函數(shù)個數(shù)k,H={h0,h1,…,hk-1},安全參數(shù)λ；

輸出 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)參數(shù)建立。客戶端C建立BFC，服務(wù)器建立GBFS并獲取GBF-M。設(shè)置集合大小m，元素個數(shù)n，安全參數(shù)λ，哈希函數(shù)H={h0,h1,…,hk-1}，分組加解密算法Enc和Dec。

2)密鑰協(xié)商。密鑰協(xié)商之前，客戶端會向服務(wù)器發(fā)送包含身份ID的請求，試圖獲得對服務(wù)器的訪問權(quán)限。服務(wù)器驗證客戶端的身份后，如果服務(wù)器同意，那么客戶端與服務(wù)器參與基于身份的密鑰協(xié)商協(xié)議，雙方共同得到分組加密的共享密鑰sk。否則服務(wù)器拒絕客戶端的請求，協(xié)議終止。

3)數(shù)據(jù)傳輸。服務(wù)器首先對GBFS作哈希運算得到hash(GBFS)，并與GBF-M提取出的hash(GBFS)進行對比，如果相同則繼續(xù)對GBFS[i]進行哈希運算，即hash(GBFS[i])，產(chǎn)生t比特輸出，然后用密鑰sk對GBFS[i]和hash(GBFS[i])分組加密得到Ei=Encsk(GBFS[i]‖hash(GBFS[i]))，否則協(xié)議停止。服務(wù)器與客戶端共同參與OT協(xié)議，服務(wù)器作為發(fā)送方將m對(λ+t)比特串(xi,0,xi,1)發(fā)送給客戶端(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個λ比特串聯(lián)接起來。

3 方案分析

3.1 安全性分析

本文方案的安全性依賴于基于身份的密鑰協(xié)商協(xié)議的安全性，以及不經(jīng)意傳輸協(xié)議的安全性。下面對該方案的安全性進行分析。

定理1 設(shè)C、S分別是客戶端與服務(wù)器的兩個集合，C∩S是兩個集合的交集，f∩是本文提出生成交集C∩S的PSI協(xié)議。如果DLP與CDH是數(shù)學(xué)困難問題，那么密鑰協(xié)商協(xié)議和不經(jīng)意傳輸協(xié)議OT是安全的，該方案能夠在惡意客戶端用戶存在的條件下安全得計算出C∩S，即：

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

綜上所述，本文方案具有抵抗惡意攻擊的安全性。

定理2 協(xié)議執(zhí)行過程中，假設(shè)安全的客戶端C嚴(yán)格按照協(xié)議得到了分組密碼密鑰sk，那么C可以根據(jù)BFC的{0,1}取值得到GBFC∩S。但是C仍可以利用BFC得到除C∩S以外的服務(wù)器S的數(shù)據(jù)內(nèi)容，用A表示此事件，則其概率為：

而ε是可以忽略的，因此C不能得到除C∩S以外的服務(wù)器S的內(nèi)容，所以協(xié)議是安全的。

證明 對于0≤i≤k-1，用ai表示事件GBFC∩S[hi(x)]等于x的第i秘密份額。如果?x∈C∩S，則p[a0∧a1∧…∧ak-1]=1，即x為C與S的交集元素時，C完全能夠?qū)計算出來。如果?x?C∩S但x∈S-C∩S，即x不是C與S的交集元素卻是S的元素時，C有可能利用BFC將x的所有秘密份額從GBFS復(fù)制到GBFC∩S中。由于x被哈希后映射到的Bloom Filter位置被設(shè)置為1，那么C就有可能將x秘密恢復(fù)出來，其概率與生成BF時的漏警率(false positive probability)的上限ε等價，于是P(A)≤ε，ε可以忽略不計，說明C即使在得到GBFS或GBFC∩S的情況下，幾乎不可能將交集以外的元素恢復(fù)出來。

如表1所示，將本文方案與文獻[1，10，13]方案進行了安全性對比。本文方案基于隨機預(yù)言機模型，能夠抵抗惡意敵手攻擊。與文獻[13]中提出的用于惡意模型的方案相比較，本文方案基于的安全假設(shè)困難性更高，更具有安全性。一方面，惡意攻擊者不能獲取到合法客戶端與服務(wù)器的數(shù)據(jù)元素；另一方面，合法客戶端用戶也不能獲得服務(wù)器除交集以外的元素，增強了安全防御與隱私保護功能。

表1 不同方案安全性對比

3.2 效率分析

如表2所示，將本文方案與文獻[1，10，13]方案的效率進行了比較分析，其中w和v分別代表客戶端集合C與服務(wù)器集合S中的元素個數(shù)。本文方案與文獻[1] 方案相比，兩者的通信復(fù)雜度相同，但是計算復(fù)雜度上本文方案有較大優(yōu)勢。本文方案與文獻[10] 方案相比，盡管兩者的通信復(fù)雜度和計算復(fù)雜度均為線性，但是本文方案中對GBF操作采用的是分組加密，而文獻[10] 方案對BF操作采用的是公鑰加密，因此本文方案在效率上較文獻[10] 方案要高。與文獻[13] 方案相比，本文方案中客戶端與服務(wù)器在構(gòu)造BFC和GBFS，以及雙方參與OT協(xié)議客戶端獲得交集的過程中，兩者的計算復(fù)雜度和通信復(fù)雜度基本相同，但較文獻[13]方案有所減少：

1)文獻[13]方案中客戶端為了獲取密鑰sk，是通過秘密共享的方式進行恢復(fù)獲取，而本文方案的sk是通過密鑰協(xié)商的方式提前獲得，減少了密鑰拆分和恢復(fù)的運算量。

2)原有方案為了驗證解密數(shù)據(jù)的正確性，客戶端事先發(fā)送給服務(wù)器一些隨機比特串，服務(wù)器接收比特串后，將其與GBFS一起加密發(fā)送給客戶端，客戶端需要比對比特串，從而達到完整性與正確性驗證的目的。而本文方案是直接對GBFS和對GBFS的哈希值進行加密，降低了加解密數(shù)據(jù)量。

表2 不同方案復(fù)雜度對比

4 結(jié)語

本文針對當(dāng)前備受關(guān)注的隱私保護問題[24]，結(jié)合隱私集合交集協(xié)議，分析了文獻[13]所提協(xié)議所存在的安全問題，并引入了密鑰協(xié)商協(xié)議和哈希算法對其進行了改進，保證了分組加密密鑰的安全性，并且針對協(xié)議的安全性和復(fù)雜度，與經(jīng)典的隱私交集協(xié)議進行了分析對比。分析結(jié)果表明本文方案能夠抵抗非法用戶的惡意攻擊，確保了雙方隱私的安全。綜合分析表明，該協(xié)議較其他相關(guān)同類協(xié)議效率更高，能夠靈活高效地應(yīng)用于隱私保護場景中。

)

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

[2] 孫茂華,宮哲.一種保護隱私集合并集外包計算協(xié)議[J].密碼學(xué)報,2016,3(2):114-125.(SUNMH,GONGZ.Aprivacy-preservingoutsourcingsetunionprotocol[J].JournalofCryptologicResearch, 2016, 3(2): 114-125.)

[3] 朱國斌,譚元巍,趙洋,等.高效的安全幾何交集計算協(xié)議[J].電子科技大學(xué)學(xué)報,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] 馮登國,張敏,李昊.大數(shù)據(jù)安全與隱私保護[J].計算機學(xué)報,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。 基金項目:國家自然科學(xué)基金資助項目(U1636114,61572521,61402531)；陜西省自然科學(xué)基金資助項目(2014JM8300,2014JQ8358,2015JQ6231,2016JQ6037)。

羅小雙(1992—),男，陜西安康人，碩士研究生，CCF會員，主要研究方向:信息安全、密碼學(xué)； 楊曉元(1959—)，男，湖南湘潭人，教授，碩士，主要研究方向：信息安全、密碼學(xué)； 王緒安(1981—)，男，湖北公安人，副教授，博士，主要研究方向：信息安全、密碼學(xué)。

1001- 9081(2017)06- 1593- 06

10.11772/j.issn.1001- 9081.2017.06.1593

TP

A