張 恩，金剛剛

(河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007)(*通信作者電子郵箱zhangenzdrj@163.com)

0 引言

隱私集合比較(Private Set Intersection, PSI)是信息安全領(lǐng)域的重要內(nèi)容，也是密碼協(xié)議設(shè)計(jì)的基本的工具，在社交網(wǎng)絡(luò)[1]、人類基因研究[2]和國家安全[3]等領(lǐng)域有著廣泛的應(yīng)用。例如，航空公司需要確定哪些乘客在禁飛的名單上，需要和國家相關(guān)部門合作，將航空公司的乘客名單與國家相關(guān)部門的禁飛名單進(jìn)行計(jì)算，最終得到禁止乘坐飛機(jī)的乘客名單，然而在上述計(jì)算過程中，需要對各方的隱私數(shù)據(jù)進(jìn)行計(jì)算，但在計(jì)算過程中可能會(huì)泄露各自的隱私數(shù)據(jù)信息，造成一些不必要的損失。如何在多方之間進(jìn)行計(jì)算得到最終結(jié)果，而在計(jì)算過程中不會(huì)泄露各方的隱私信息成為了非常緊迫和嚴(yán)峻的問題。

隱私集合比較[4-5]主要解決在多方參與的情況下計(jì)算出各方集合的比較結(jié)果，且不泄露除比較結(jié)果以外的參與者的隱私信息。2004年，F(xiàn)reedman等[6]提出了在半誠實(shí)模型和惡意模型下基于同態(tài)加密和哈希平衡的兩方隱私集合交集協(xié)議；2005年，Kissner等[7]提出了更有效的安全多方計(jì)算協(xié)議，實(shí)現(xiàn)了隱私集合交集計(jì)算。與以上協(xié)議相比，李順東等[8]和Cristofaro等[9]分別提出了一個(gè)效率較高的隱私集合交集協(xié)議，協(xié)議具有線性復(fù)雜度，需要公鑰加密運(yùn)行。張恩等[10]提出了基于博弈論與密碼學(xué)理論的、理性的安全兩方計(jì)算協(xié)議，能確保安全兩方計(jì)算的公平性。之后Zhang等[11]提出了基于聲譽(yù)系統(tǒng)的服務(wù)器輔助的隱私集合交集協(xié)議，該協(xié)議允許參與各方使用不同的加密密鑰，不需要公共密鑰基礎(chǔ)設(shè)施，最終所有的用戶都可公平地得到計(jì)算結(jié)果。Dong等[12]提出了基于混淆布隆過濾器(Bloom Filter, BF)和密鑰共享的隱私集合交集協(xié)議。Kamara等[13]提出了一種服務(wù)器輔助的隱私集合交集協(xié)議，將隱私集合交集的計(jì)算量提升到億級。Chen等[14]提出一種針對惡意敵手的隱私集合交集協(xié)議，該協(xié)議具有線性復(fù)雜度與較小通信復(fù)雜度。Rindal等[15]認(rèn)識到Dong等[16]的協(xié)議中惡意安全版本存在錯(cuò)誤，介紹了如何使用具有低開銷的方法，同時(shí)避免原始協(xié)議中的主要計(jì)算瓶頸。Kerschbaum等[17]結(jié)合BF和Goldwasser-Micali同態(tài)加密，提出一個(gè)半誠實(shí)版本的兩方協(xié)議，但協(xié)議需要多個(gè)哈希操作，且需要對BF中的每一個(gè)元素進(jìn)行擴(kuò)展，計(jì)算量較大。

為解決目前多方隱私集合比較協(xié)議計(jì)算效率較低且在云環(huán)境下會(huì)泄露用戶隱私信息的問題，將同態(tài)加密與BF應(yīng)用于多方隱私集合比較協(xié)議，協(xié)議的計(jì)算復(fù)雜度是線性的，計(jì)算效率較高。該協(xié)議使用同態(tài)加密算法，使用戶可以用不同的公鑰將各自的信息加密并上傳給云服務(wù)器，云服務(wù)器對密文進(jìn)行計(jì)算，確保隱私集合比較的計(jì)算可以安全高效地進(jìn)行；同時(shí)，使用基于NTRU的代理重加密算法解決了云服務(wù)器無法對不同公鑰加密的密文進(jìn)行計(jì)算的問題。該協(xié)議借助BF存儲、計(jì)算效率較高的優(yōu)點(diǎn)能提高協(xié)議的運(yùn)行效率。

1 基礎(chǔ)知識

1.1 隱私集合交集

1.2 Bloom過濾器

目前隨著信息的增長，人們使用各種信息存儲方法，但是信息的存儲對軟硬件的要求越來越高，信息的插入、存取和查詢等操作也越來越麻煩，針對這一問題國內(nèi)外學(xué)者研究出了一種空間利用效用高、存取和查詢方便的BF[18]。BF的大小與元素自身的大小無關(guān)，只與元素映射到表中的個(gè)數(shù)有關(guān)，BF有計(jì)算復(fù)雜度低、空間利用率高和查詢效率高等優(yōu)點(diǎn)，適合在現(xiàn)實(shí)中應(yīng)用。BF元素插入查詢過程如圖1所示。

圖1 BF元素插入查詢示意圖

BF是一種支持存儲和查詢的數(shù)據(jù)結(jié)構(gòu)，存在哈希函數(shù)H={h1,h2,…,hk}，集合中的元素被k個(gè)均勻獨(dú)立的哈希函數(shù)映射到m個(gè)索引號中，并且對應(yīng)位置的值被設(shè)置為1。

1)插入操作：將集合中一個(gè)元素x進(jìn)行k次哈希得到k個(gè)哈希值h1(x),h2(x),…,hk(x)添加到BF對應(yīng)位置中，再把BF的k個(gè)對應(yīng)位置的值全部設(shè)置為1，即BF[h1(x)]=BF[h2(x)]=…=BF[hk(x)]=1。

2)查詢操作：為查詢元素x是否存儲在BF中，計(jì)算元素x的k個(gè)哈希值h1(x),h2(x),…,hk(x)，然后檢查BF中對應(yīng)位置的值是否都為1。如果其中有一個(gè)為0，則元素x沒有存儲在BF中；如果都為1,則元素x存儲在BF中，這種情況稱為BF的假陽性誤判，即將不屬于集合中的元素誤判為該元素集合中的元素。

(1)

1.3 Paillier同態(tài)加密

Paillier同態(tài)加密[20]是一個(gè)概率公鑰算法，由密鑰生成、加密和解密三部分組成。

1)密鑰生成：隨機(jī)選取兩個(gè)大素?cái)?shù)p和q，

gcd(pq,(p-1)(q-1))=1

(2)

計(jì)算:

n=pq

(3)

λ=lcm(p-1,q-1)

(4)

挑選一個(gè)隨機(jī)整數(shù)g，計(jì)算:

μ=(L(gλ(modn2)))-1(modn)

(5)

其中:L(x)=(x-1)/n；公鑰pk為(n,g)，私鑰sk為(λ,μ)。

3)解密: 密文為c，計(jì)算m=L(cλ(modn2))μmodn。

gm1+m2(r1r2)nmodn2=E(pk,m1+m2)

(6)

1.4 代理重加密

代理重加密[21]是密文之間的密鑰轉(zhuǎn)換機(jī)制，由Blaze等于1998年在歐洲密碼學(xué)年會(huì)上提出。代理重加密算法允許一個(gè)代理者將Alice的公鑰加密的密文轉(zhuǎn)換為由Bob的公鑰加密的密文，代理者不能從被加密的信息和重加密密鑰中得到任何明文的信息。受理者除非得到重加密密文，否則無法得到任何關(guān)于明文的信息。具體工作方式為：Alice或者一個(gè)可信第三方計(jì)算出重加密密鑰發(fā)送給代理者，當(dāng)代理者接收到Alice的加密信息時(shí)調(diào)用重加密算法，把已經(jīng)轉(zhuǎn)換的密文發(fā)送給Bob，Bob接收到之后再用自己的私鑰進(jìn)行解密計(jì)算得到明文。

基于NTRU的代理重加密算法[22]由KeyGen、ReKeyGen EnCrypt、ReEncrypt和DeCrypt構(gòu)成：

3)EnCrypt(pkA,M):輸入公鑰pkA與消息M∈RNTRU/q，使用加密算法EnCrypt產(chǎn)生一個(gè)隨機(jī)多項(xiàng)式s∈RNTRU，并輸出密文CA=hAs-M。

4)ReEncrypt(rkA→B,CA):輸入一個(gè)代理重加密密鑰rkA→B與密文CA，使用代理重加密算法ReEncrypt選取一個(gè)多項(xiàng)式e∈RNTRU并輸出密文CB=CArkA→B+pe，其中e∈RNTRU。

1.5 半誠實(shí)模型

半誠實(shí)模型[23]中所有的參與者都會(huì)準(zhǔn)確地執(zhí)行協(xié)議，但在協(xié)議執(zhí)行過程中會(huì)記錄下所有中間結(jié)果，以便推算出其他有用信息。敵手會(huì)腐敗部分參與者，并根據(jù)腐敗參與者的輸入信息推導(dǎo)出更多信息，但不能對信息進(jìn)行修改。

定義1 令π表示隱私集合比較協(xié)議，F(xiàn)表示理想模型下的函數(shù)。假如對于現(xiàn)實(shí)模型下任意概率多項(xiàng)式時(shí)間敵手A，都存在理想模型下敵手SIM，使得協(xié)議π在理想與現(xiàn)實(shí)情況下計(jì)算不可區(qū)分，即對于參與方Pj、S1和S2滿足：

(7)

則稱協(xié)議π可以安全計(jì)算F。

2 本文方案

2.1 用戶創(chuàng)建BF階段

用戶Pj(1≤j≤N)擁有集合Xj={xj,1,xj,2,…,xj,lj},對集合Xj中每一個(gè)元素使用k個(gè)均勻分布的哈希函數(shù)H={h1,h2,…,hk}進(jìn)行哈希，然后將BF中對應(yīng)索引位置的值設(shè)置為1，用戶Pj(1≤j≤N)分別得到各自的長度為m的Bloom過濾器BFj。生成BF的算法如算法1所示。

算法1 Bloom過濾器BFj生成算法。

輸入 BF長度為m，數(shù)據(jù)集合為C，集合元素個(gè)數(shù)為n，哈希函數(shù)個(gè)數(shù)為k，H={h1,h2,…,hk}；

輸出BFj。

fori=1 toi=m-1

BFj[i]=0

//將m個(gè)位置設(shè)置為0

end

for eachx∈C

//插入集合元素x

fori=1 toi=k

l=hi(x)

//將x哈希為k個(gè)索引值

ifBFj[l]=0 then

BFj[l]=1

end

end

2.2 生成轉(zhuǎn)換密鑰階段

(8)

(9)

2.3 云服務(wù)器計(jì)算階段

圖2 服務(wù)器計(jì)算階段BF示意圖

(10)

2.4 用戶計(jì)算查詢階段

算法2 BF查詢算法。

輸入 元素集合C，哈希函數(shù)個(gè)數(shù)k，H={h1,h2,…,hk}；

輸出 比較結(jié)果X1∩X2∩…∩XN。

for eachx∈C

fori=1 toi=k

ifBF[hi(x)]=N

//判斷hi(x)處元素是否為N

j=1

else

j=0

end

ifj=1

//BF中對應(yīng)元素為N

continue

else break

end

end

ifi=kthenx∈X1∩X2∩…∩XN

//x為比較結(jié)果

else break

end

3 安全性分析

本文提出的多方隱私集合比較協(xié)議假設(shè)云服務(wù)器S1和S2是半誠實(shí)的且不會(huì)合謀，協(xié)議的安全性證明如下：

提出的基于同態(tài)加密的多方隱私集合比較協(xié)議在以下三個(gè)場景中是安全的：腐敗的用戶Pj(1≤j≤N)與誠實(shí)的云服務(wù)器S1和S2；誠實(shí)的用戶Pj(1≤j≤N)、腐敗的云服務(wù)器S1與誠實(shí)的云服務(wù)器S2；誠實(shí)的用戶Pj(1≤j≤N)、誠實(shí)的云服務(wù)器S1與腐敗的云服務(wù)器S2。

模擬器SIM的執(zhí)行過程描述如下：令C為腐敗用戶的集合，H為誠實(shí)用戶的集合，模擬器SIM黑盒調(diào)用敵手A。

構(gòu)建一個(gè)模擬器SIM3，模擬器SIM3調(diào)用敵手A腐敗云服務(wù)器S2，模擬器SIM3模擬云服務(wù)器S2在協(xié)議執(zhí)行過程中的相應(yīng)操作，最終模擬器SIM3把rjfjmodq發(fā)送給敵手A，模擬器SIM3輸出與敵手A相同的輸出。根據(jù)Paillier算法的安全性可知模擬器SIM3和敵手A無法獲得用戶的隱私信息和最終結(jié)果，根據(jù)NTRU的代理重加密協(xié)議的安全性，模擬器SIM3的全局輸出和A的視圖在理想模型和現(xiàn)實(shí)模型下是不可區(qū)分的。

綜上所述，可得：

(11)

4 性能比較

對方案在通信復(fù)雜度與計(jì)算復(fù)雜度及其他方面進(jìn)行了分析，然后和其他隱私集合相關(guān)協(xié)議進(jìn)行了比較，本文協(xié)議中用戶將自己的集合元素分別存儲在各自的BF中，每個(gè)用戶均需要進(jìn)行l(wèi)jk(1≤j≤N)次哈希操作與m次加密操作，m表示BF長度，lj(1≤j≤N)表示用戶集合元素個(gè)數(shù)，用戶對BF進(jìn)行逐位解密需要m次操作。

表1將與本文相關(guān)的幾種隱私集合交集協(xié)議進(jìn)行了對比。文獻(xiàn)[7]中提出了在半誠實(shí)和惡意模型下基于同態(tài)加密和哈希平衡的兩方隱私集合交集協(xié)議，協(xié)議使用數(shù)據(jù)元素作為多項(xiàng)式的根，而且在計(jì)算過程中不會(huì)泄露多項(xiàng)式的系數(shù)，通信復(fù)雜度是O(v+w)，計(jì)算復(fù)雜度是O(wlog logv)，其中v為用戶個(gè)數(shù)，w為服務(wù)器的個(gè)數(shù)。文獻(xiàn)[13]中提出了基于不經(jīng)意傳輸與BF的隱私集合交集協(xié)議，該協(xié)議需要一個(gè)半誠實(shí)的云服務(wù)器，而且只能進(jìn)行兩方計(jì)算，不能進(jìn)行多個(gè)用戶之間的計(jì)算，最終只有一方能得到結(jié)果，在協(xié)議運(yùn)行過程中需要用戶之間進(jìn)行多次交互，使通信復(fù)雜度增加。文獻(xiàn)[14]中針對億級數(shù)據(jù)量的情況分別提出了在半誠實(shí)模型與惡意模型下的隱私集合交集協(xié)議，該協(xié)議需要用戶之間進(jìn)行交互產(chǎn)生同樣的密鑰進(jìn)行加解密，安全性有所欠缺，另外協(xié)議最終會(huì)泄露交集大小。文獻(xiàn)[17]中將BF和Goldwasser-Micali同態(tài)加密結(jié)合在一起，這是一個(gè)半誠實(shí)版本的兩方協(xié)議，需對BF中的元素進(jìn)行擴(kuò)展，計(jì)算量較大。

表1 不同方案的性能對比

5 結(jié)語

本文針對隱私集合比較協(xié)議的安全性和效率問題進(jìn)行分析和研究，提出基于同態(tài)加密與BF的云外包多方隱私集合比較協(xié)議，協(xié)議中使用基于NTRU的代理重加密算法可以使用戶用不同的公鑰對各自的隱私信息進(jìn)行加密，然后用戶將密文上傳給云服務(wù)器，云服務(wù)器對密文進(jìn)行相關(guān)計(jì)算，提高協(xié)議的安全性。協(xié)議將大量的計(jì)算外包給云服務(wù)器，用戶僅需進(jìn)行少量操作。理論分析及運(yùn)算結(jié)果表明，協(xié)議的計(jì)算復(fù)雜度和通信復(fù)雜度是線性的，可在避免泄露用戶隱私信息的前提下獲得最終比較結(jié)果，靈活高效地應(yīng)用于現(xiàn)實(shí)生活。下一步工作是對協(xié)議進(jìn)行改進(jìn)和優(yōu)化，使提出的協(xié)議能抵御惡意模型下攻擊者對數(shù)據(jù)集的攻擊。