魏立斐 劉紀海 張 蕾 王 勤 賀崇德

(上海海洋大學信息學院 上海 201306)

隨著互聯(lián)網(wǎng)大數(shù)據(jù)時代的到來，人們通過對大量分布的數(shù)據(jù)進行挖掘得到其潛在價值，從而更好地服務于人們，如用戶愛好推薦系統(tǒng)、廣告精準營銷等.然而，在挖掘數(shù)據(jù)潛在價值的過程中，也會產(chǎn)生個人隱私數(shù)據(jù)泄露等問題，如英國咨詢公司劍橋分析公司在未經(jīng)Facebook用戶同意的情況下獲取數(shù)百萬用戶的個人數(shù)據(jù).因此，實現(xiàn)數(shù)據(jù)可用不可見，解決數(shù)據(jù)協(xié)同計算和挖掘過程中的數(shù)據(jù)安全和隱私保護問題就顯得迫在眉睫.相關國家和組織也出臺保護隱私數(shù)據(jù)的法令法規(guī)，如《中華人民共和國密碼法》《中華人民共和國數(shù)據(jù)安全法》《中華人民共和國個人信息保護法》和歐盟《通用數(shù)據(jù)保護條例》都強調(diào)對數(shù)據(jù)的治理和隱私保護.數(shù)據(jù)隱私保護已成為學術界和工業(yè)界關注的熱點問題.

隱私數(shù)據(jù)保護最早源于安全多方計算(secure multiparty computation, MPC)，由姚期智[1]借百萬富翁問題提出，指各計算參與方無法得到除計算結果外的任何其他信息，解決互不信任的數(shù)據(jù)持有者如何對隱私數(shù)據(jù)進行計算的問題.隱私集合交集(private set intersection, PSI)是安全多方計算中的熱點問題，允許在分布式場景下各自持有隱私集合的參與方聯(lián)合計算出集合交集而不泄露除交集以外的任何隱私信息.在隱私保護的場景中，PSI協(xié)議具有重要意義，如新冠接觸者追蹤[2]、隱私通訊錄查找[3]、在線廣告實際效果計算[4]、基因序列匹配檢測[5]等.

傳統(tǒng)的PSI協(xié)議針對2個參與方設計，Meadows[6]基于公鑰加密和利用Diffie-Hellman密鑰交換的乘法同態(tài)性質(zhì)提出了第1個PSI協(xié)議.隨后，由Huberman等人[7]對Meadows[6]的方案做出了完整描述.2004年由Freedman等人[8]借助不經(jīng)意多項式求值和同態(tài)加密構造了第1個安全PSI協(xié)議.2017年申立艷等人[9]對安全多方計算框架下的PSI協(xié)議進行了簡要總結.之后涌現(xiàn)了大量PSI的研究成果，一大批新技術手段和構造框架被提出.除了傳統(tǒng)的安全多方計算理論中的混淆電路(garbled circuit, GC)、不經(jīng)意傳輸(oblivious transfer, OT)、秘密共享(secret sharing, SS)、同態(tài)加密(homomorphic encryption, HE)等技術外，不經(jīng)意偽隨機函數(shù)(oblivious pseudo-random function, OPRF)、不經(jīng)意多項式求值(oblivious polynomial evaluation, OPE)、布隆過濾器(Bloom filter, BF)等集合元素比較技術的應用，使得PSI的效率得到了很大的提高.

現(xiàn)有PSI已經(jīng)非常高效，但現(xiàn)有很多實際應用中仍然以使用高效但存在安全隱患的解決方案為主，了解現(xiàn)有基于不同密碼原語構建的PSI及其特定適用場景，對促進實際場景中使用安全的方案替換存在隱患的方案有很大幫助.在敵手模型方面，研究人員從誠實且好奇的安全模型出發(fā)，開始考慮在惡意模型下安全的PSI協(xié)議.隨著研究人員對隱私集合交集協(xié)議的深入研究，除了傳統(tǒng)兩方PSI協(xié)議之外，已衍生出了云輔助PSI、閾值PSI(threshold PSI，TPSI)、不平衡PSI(unbalanced PSI，UPSI)和多方PSI新型應用場景.

本文首先介紹PSI協(xié)議的理論基礎、敵手模型、安全證明、實現(xiàn)框架，其次系統(tǒng)總結了傳統(tǒng)PSI協(xié)議的設計框架，隨后介紹PSI協(xié)議中的集合元素比較技術，進一步詳細闡述了適應新型應用場景的PSI方案，最后總結并展望面向隱私保護的集合交集計算中亟待解決問題和發(fā)展方向.

1 基礎知識

1.1 密碼技術

1.1.1 秘密共享

秘密共享技術是許多安全多方計算協(xié)議的核心.如何構建秘密分配算法和秘密重構算法是秘密共享方案的重點.Shamir[10]提出的(k,n)秘密共享方案基于多項式插值構建秘密分配算法和秘密重構算法，通過控制多項式的未知系數(shù)實現(xiàn)閾值門限.Blakley[11]秘密共享方案基于線性幾何投影實現(xiàn).Jia等人[12]秘密共享方案基于中國剩余定理實現(xiàn).除了在特定環(huán)境下的門限秘密共享方案外，研究者們還設計了安全多方計算環(huán)境下的(n,n)秘密共享方案，可直接在比特碎片上進行相應的計算.

1.1.2 同態(tài)加密

同態(tài)加密允許對密文進行加或乘的操作，滿足密文計算后的解密值和明文計算的結果相同.由于整個計算過程是在密文的基礎上進行，故同態(tài)加密往往被用做外包計算的隱私保護工具.同態(tài)加密方案由4個算法組成: KeyGen算法生成公鑰和私鑰、Encrypt算法加密明文、Decrypt算法解密密文、Evaluate算法計算密文.同態(tài)加密根據(jù)同態(tài)性質(zhì)可分為加法同態(tài)加密(Paillier加密[13])、乘法同態(tài)加密(RSA加密[14]、ElGamal加密[15])、全同態(tài)加密(FHE[16]).盡管目前全同態(tài)加密算法的效率不足以應用于實際場景，但其支持直接密文計算的性質(zhì)使得同態(tài)加密仍受到學術界和工業(yè)界的重點關注.

1.1.3 不經(jīng)意傳輸

Crépeau[18]提出隨機不經(jīng)意傳輸協(xié)議(random oblivious transfer, ROT)，ROT協(xié)議分為離線-在線階段，離線階段通過少量OT使得發(fā)送方接收隨機消息對(r0,r1)，接收方接收隨機選擇位(b,rb).在線階段雙方只需使用隨機消息對對真實輸入進行盲化而無需進行昂貴的公鑰操作.Beaver[19]提出非黑盒子構造，實現(xiàn)Yao[1]協(xié)議中通過少量公鑰操作生成大量OT實例.Ishai等人[20]依據(jù)矩陣變化思想實現(xiàn)用少量公鑰轉(zhuǎn)化為大量OT實例.Kolesnikov等人[21]對OT擴展矩陣進行重復編碼實現(xiàn)1-out-of-nOT.2013年Asharov等人[22]提出了2種OT擴展優(yōu)化和OT相關變體.Boyle等人[23]基于Vector-OLE關聯(lián)的偽隨機發(fā)送器和基于LPN假設提出Silent OT擴展(Boyle等人[23]、Schoppmann等人[24]、Weng等人[25]、Yang等人[26])，離線階段雙方執(zhí)行相關OT生成相關短種子，本地利用PCG將相關短種子無交互的局部擴展為大量相關隨機性長源，在線階段即可利用長源執(zhí)行多個ROT，大大降低通信復雜度.

1.1.4 混淆電路

混淆電路是一種將任意功能函數(shù)轉(zhuǎn)化為電路的通用型基礎協(xié)議.通過混淆電路表和OT加密電線值實現(xiàn)安全隱私保護.混淆電路的構造思路主要分為3種:1)通過電路混淆者持有2個可能的電線標簽，電路評估者持有標簽，間接實現(xiàn)電線值秘密共享的Yao[1]協(xié)議.2)電路評估者直接持有電線值的秘密份額的GMW[27]協(xié)議.3)秘密不再由參與者之間秘密共享而是在電線之間共享，如基于信息安全論構造協(xié)議[28].目前混淆電路的研究主要涉及擴展安全模型(如半誠實模型擴展為惡意模型)、減少密文尺寸(如點置換協(xié)議[29]、密文混淆協(xié)議[30]、免費異或門[31])和降低計算代價.

1.1.5 Hash技術

Hash技術是PSI協(xié)議中優(yōu)化通信復雜度和計算復雜度的重要工具之一，本文列舉了最常用的Hash技術構造方法.

1) 樸素Hash(plain Hash).使用hashk(·)將元素映射到具有b個桶的Hash表T中的k個位置，每個桶最多有l(wèi)b(n)個元素(n為集合的元素個數(shù)).hashk(·)表示k個不同的Hash函數(shù)h1(·)，h2(·),…,hk(·).

2) 布谷鳥Hash(cuckoo Hash)[32].使用hashk(·)將元素e映射到具有b個桶的Hash表T中的某一個位置，確保每個桶只能有1個元素:計算h1(e)，h2(e)，…，hk(e)，如果T[h1(e)]，T[h2(e)]，…，T[hk(e)]至少有1個桶為空，則隨機插入；如果都不為空，則隨機選擇T[hi(e)]，替換桶中的元素T[hi(e′)]，再對被替換元素e′執(zhí)行上述操作.當上述替換操作達到一定閾值時，則將e′放置在額外的存儲空間stash中.因此，元素e必定在以下容器中找到:T[h1(e)]，T[h2(e)]，…，T[hk(e)]或stash.由于stash可能會存在溢出威脅而導致Hash錯誤，Pinkas等人[33]通過實驗分析出Hash函數(shù)個數(shù)、stash大小和桶數(shù)b的最佳關系.

3) 置換Hash(permutation-based Hash)[34].將元素轉(zhuǎn)化為更短的字符串并存儲在Hash表中，以此減少存儲空間和計算復雜度.元素插入如下:元素x表示為bit的形式并拆分為2部分x1，x2.為元素獲取Hash表的索引:x1⊕H(x2)，H為Hash函數(shù),⊕表示按位異或.最后桶中存儲大小為|x2|=|x|-|x1|.|x|表示x的比特長度.

1.2 敵手模型

敵手模型由2個主要方面構成:允許敵手的行為方式和腐敗策略.根據(jù)敵手是否指示參與方行事可分為半誠實模型、增強半誠實模型、惡意模型.半誠實模型:即使被敵手腐敗的參與方也會誠實地執(zhí)行協(xié)議，但在執(zhí)行過程中會主動收集相關信息，并試圖利用這些信息學習協(xié)議中的保密信息.增強半誠實模型:在半誠實模型基礎上，允許敵手更改起始輸入，但在其他輸入上誠實地執(zhí)行協(xié)議.惡意模型:允許敵手控制的參與方根據(jù)敵手的指示執(zhí)行協(xié)議，偏離原本協(xié)議.

根據(jù)參與方何時處于敵手的控制可分為靜態(tài)腐敗模型、自適應腐敗模型、主動安全模型.靜態(tài)腐敗模型:敵手控制的參與方固定，誠實的參與方從協(xié)議開始到結束始終是誠實的，腐敗方始終是腐敗的.自適應腐敗模型:在整個協(xié)議執(zhí)行過程中，敵手可依據(jù)需求選擇何時腐敗和被腐敗的參與者.但腐敗后的參與者將一直保持腐敗模式到協(xié)議結束.主動安全模型:參與方只在一段時間內(nèi)可能被敵手控制，誠實的一方可能會變得腐敗，腐敗的一方也可能變得誠實.

1.3 安全性證明方法

理想/真實模擬范式[35]是安全多方計算協(xié)議最常用的一種證明方法，通過模擬具有安全保證的理想模型與現(xiàn)實PSI協(xié)議比較，間接證明其安全性.通過定義理想模型相關的安全目標，避免協(xié)議設計過程中安全目標的不完整性.理想模型由完全受信任的三方計算功能函數(shù)，并將結果返回給參與方.真實模型通過PSI協(xié)議將功能函數(shù)拆分為多個消息函數(shù)并在參與方之間相互交流完成計算.最后理想模型的視圖與真實模型的視圖達到不可區(qū)分來證明PSI協(xié)議的安全性.

1.4 編程框架

借助MPC通用編譯器，改善PSI現(xiàn)有技術，減輕設計自定義協(xié)議的負擔，幫助研究人員快速建立協(xié)議實驗.本文從支持輸入語言、參與方數(shù)量、敵手模型和所支持的協(xié)議進行簡要總結如表1所示，具體詳情可參考文獻[36].

Table 1 MPC Framework Comparison表1 MPC框架對比

2 隱私集合交集的設計框架

2.1 基于公鑰加密的設計框架

隱私集合交集協(xié)議早期思想直接對元素進行加密，然后在密文上進行相應的比較操作.其最常用的技術是同態(tài)加密，發(fā)送方加密集合發(fā)送給接收方.接收方利用同態(tài)加密的性質(zhì)對密文進行計算，并將計算結果發(fā)給發(fā)送方，發(fā)送方利用私鑰對其解密并得到集合交集.基于公鑰加密的安全性假設主要分為3類:

1) 基于DH(Diffie-Hellman)假設.Meadows[6]基于離散對數(shù)困難問題實現(xiàn)DH密鑰交換協(xié)議并以此實現(xiàn)PSI功能，Huberman等人[7]發(fā)現(xiàn)基于橢圓曲線密碼的PSI相較于基于離散對數(shù)密碼的PSI具有更高的安全性和高效性.

2) 基于RSA假設.De Cristofaro等人[42]基于整數(shù)分解困難問題的RSA盲簽名技術實現(xiàn)半誠實PSI協(xié)議，文獻[43]分析基于離散對數(shù)密碼的PSI協(xié)議比基于整數(shù)分解密碼的PSI協(xié)議更加高效.

3) 基于同態(tài)加密.Freedman等人[8]將元素表示為多項式的根，利用Paillier同態(tài)加密技術加密多項式系數(shù)和零知識證明實現(xiàn)兩方惡意攻擊安全的PSI協(xié)議，2016年Freedman等人[44]使用ElGamal加密加快計算效率和布谷鳥Hash技術降低計算復雜度.Kissner等人[45]采用不同的多項式表示方法將計算開銷下降到與參與人數(shù)呈線性關系.Hazay等人[46]構建一個具有門限解密的加法同態(tài)加密方案實現(xiàn)多方半誠實PSI協(xié)議.Abadi等人[47]提出基于點-值對的d次多項式表示集合方法，通過Paillier加密方案完成，將乘法復雜度從O(d2)下降到O(d).Jarecki 等人[48]使用加法同態(tài)加密和零知識證明來實現(xiàn)偽隨機函數(shù)(pseudo-random function, PRF).竇家維等人[49]基于有理數(shù)編碼和三角形面積計算公式并結合Paillier加密實現(xiàn)有理數(shù)上的PSI協(xié)議.基于公鑰加密的PSI協(xié)議一般具有較小的通信輪數(shù)，適用于具有較強計算能力的模型，但通信帶寬和時間復雜度是實際應用中一個很大的瓶頸障礙.

2.2 基于混淆電路的設計框架

混淆電路可將任意函數(shù)轉(zhuǎn)化為布爾電路，再進行通用的安全計算.早期基于通用電路的設計方案DPSZ[50]描述了基于算術電路實現(xiàn)集合求交問題:電路生成者通過對稱密鑰對電路門進行加密，再生成混淆電路并將混淆電路發(fā)送給電路評估者；電路評估者對混淆電路對應線路進行解密得到交集，且得不到電路中其他線路的任何信息.其構造的復雜度隨電路深度的增加而增加.本文主要討論專用的電路PSI協(xié)議，即在預處理階段減少電路的比較次數(shù)和電路的深度，電路階段只進行元素的相等性測試以實現(xiàn)通用的PSI協(xié)議，并可在電路PSI協(xié)議的基礎上執(zhí)行對稱函數(shù)(交集基數(shù)、交集和、閾值-交集).混淆電路有2種抵抗半誠實敵手的電路Yao[1]協(xié)議和GMW[27]協(xié)議.Huang等人[51]對元素進行特定排序，通過Yao電路合并后進行相鄰元素的相等性測試，構造出排序比較亂序電路實現(xiàn)半誠實安全的PSI協(xié)議.Pinkas等人[52-54]和Chandran等人[55]基于GMW電路和Hash存儲結構進行隱私集合的成員測試構造出OPRF電路實現(xiàn)半誠實安全PSI協(xié)議.上述方案通過Hash技術降低比較次數(shù)，通過隱私成員測試協(xié)議降低電路等值比較的深度，使得電路PSI越來越高效.然而，此類協(xié)議需要額外的密鑰計算過程和通信，如參與方需要密鑰協(xié)商等.

2.3 基于不經(jīng)意傳輸?shù)脑O計框架

基于不經(jīng)意傳輸技術構造PSI協(xié)議通過隨機值盲化集合元素產(chǎn)生隱私保護效果.構造思想:首先將集合元素通過特定數(shù)據(jù)結構存儲，然后雙方為每一個桶運行OT協(xié)議:發(fā)送方使用隨機值盲化集合元素并將盲化結果發(fā)送給接收方，接收方在本地執(zhí)行相等性測試得到隱私集合交集.由于需要使用大量的OT，傳統(tǒng)OT協(xié)議限制了PSI協(xié)議的安全性和效率性，通過OT擴展技術(oblivious transfer extension, OTE)可有效解決該瓶頸.OTE依據(jù)設計思想可分為2類:1)基于矩陣變換的思想利用少量公鑰OT實現(xiàn)大量OT實例的IKNP-OT.依據(jù)抵御敵手行為能力可分為半誠實安全模型OT協(xié)議[20]和惡意安全模型OT協(xié)議[56].文獻[57]基于布隆過濾器和IKNP03-OT[20]構造出半誠實PSI協(xié)議.Pinkas等人[43]將文獻[57]中OT協(xié)議換為ALSZ13-OT[22]使接收方到發(fā)送方的通信量減少一半.文獻[58-59]將文獻[57]中OT協(xié)議換為KSO15-OT[56]并結合Cut-and-Choose技術，以確保Dong協(xié)議中的發(fā)送方輸入不能明顯多于其BF中1的數(shù)量，實現(xiàn)惡意攻擊安全的PSI協(xié)議.文獻[60]對文獻[58]的k-out-of-nOT參數(shù)進行改進提供了更好的安全保證.Kolesnikov等人[61-62]、Pinkas等人[63]、Chase等人[64]分別基于1-out-of-nKK13-OT[21]和偽隨機函數(shù)構造出單點OPRF、不經(jīng)意可編程偽隨機函數(shù)(oblivious programmable pseudorandom function, OPPRF)、多點OPRF(multi-point OPRF, mOPRF)、帶權多點OPRF實現(xiàn)具有半誠實安全的PSI協(xié)議.Pinkas等人[65]基于OOS17-OT協(xié)議[66]構造具有惡意安全的PSI協(xié)議.2)基于子向量不經(jīng)意線性評估實現(xiàn)具有更低的通信效率但計算復雜度增加的Silent-OT.Rindal等人[67]基于半誠實安全的Schoppmann等人[24]協(xié)議和惡意安全的Weng等人[25]協(xié)議分別構造出半誠實安全和惡意安全的PSI協(xié)議.基于OT的PSI協(xié)議一般具有較低通信和計算量，本文依據(jù)設計思想、功能和安全模型對現(xiàn)有PSI協(xié)議進行分類如表2所示：

Table 2 PSI Protocols Based on OT Framework表2 基于OT框架的PSI協(xié)議

3 隱私集合元素比較技術/工具

3.1 不經(jīng)意偽隨機函數(shù)

利用OPRF設計PSI協(xié)議是一種常見的思想.OPRF允許接收方輸入x，發(fā)送方輸入密鑰k，接收方輸出Fk(x)，發(fā)送方無任何輸出.然后發(fā)送方本地計算Fk(y)并將其發(fā)送給接收方.接收方通過比較Fk(x)和Fk(y)可以構造出PSI.基于OPRF構造PSI的論文進展如圖1所示：

Fig. 1 The progress of OPRF based PSI protocols圖1 基于OPRF的PSI論文進展

Naor等人[72]基于Diffie-Hellman假設和標準1-out-of-2 OT構造出第1個OPRF，Hazay等人[73]利用上述OPRF實現(xiàn)安全的PSI協(xié)議，滿足單邊惡意敵手模型，但其使用的是非單向映射的PRF，可能會因惡意選擇PRF密鑰而產(chǎn)生沖突.Jarecki等人[48]基于Dodis-Yampolskiy[74]提出的具有O(1)指數(shù)冪的單射偽隨機函數(shù):fk(x)=g1/(k+x)和Paillier同態(tài)加密完成OPRF構建.協(xié)議需要多個模N2的指數(shù)運算，導致計算量非常大.Debnath等人[75]通過零知識證明技術和引入半可信第三方，構造出雙方獲取交集結果的OPRF.Jarecki等人[76]基于不可預測函數(shù):fk(x)=(H(x)k)和Hash函數(shù)完成OPRF:fk(x)=H′(H(x),H(x)k)構建.構造PSI協(xié)議:P2使用隨機值a盲化H(x)得到y(tǒng)=H(x)a并將其發(fā)送給P1.P1使用密鑰k加密y得到z=yk并將其發(fā)送給P2.P2即可得到fk(x)=z/a=H(x)k.通過外層Hash函數(shù)和對密鑰k進行零知識證明以抵抗惡意敵手的攻擊.

Kolesnikov等人[61]基于隨機OT[20]協(xié)議改進了1-out-of-2 OT擴展并結合對稱密鑰和位運算構造出單點OPRF:fk(x)=H(q⊕[C(x)∧s])(其中密鑰k由q,s∈{0,1}n組成，∧表示按比特位與操作):雙方首先通過布谷鳥hashk將集合映射到布谷鳥Hash表中，以降低比較次數(shù).再對每一個桶執(zhí)行單點OPRF操作，P2隨機均勻采樣字符串r0={0,1}n計算r1=r0⊕C(y)，P1隨機采樣字符串s={0,1}n.雙方分別輸入r1和s執(zhí)行n輪OT，最后P1接收n位{rs[j][i]}i∈n,s[j]∈{0,1}.P1計算q=rs[1][1]‖rs[2][2]‖…‖rs[n][n]得到OPRF密鑰k=(q,s).P2輸入y到OPRF輸出值H(r0).如果x=y，則q⊕[C(x)∧s]=r0，即得到交集.

由于文獻[61]中每個元素被多個Hash函數(shù)映射，從而導致每個元素都需執(zhí)行多個單點OPRF操作.Pinkas等人[63]通過多項式插值技術結合IKNP-OT設計了1個稀疏OT擴展，其允許接收方從n個隨機秘密中不經(jīng)意地選取k個以此實現(xiàn)多點OPRF(multi-point OPRF, mOPRF)，即實現(xiàn)每一個元素只需要1個OPRF操作.該協(xié)議通過選擇與稀疏OT吻合的Hash結構:2-選擇Hash[77]，不需要偽隨機填充值，且每個桶可放入多個元素，使得比較次數(shù)下降.但是與文獻[61]相比，mOPRF需要在1個大的域上計算和插值1個高階多項式從而產(chǎn)生較高的計算開銷，比文獻[61]僅使用對稱密碼和位運算要花費更多的成本.Chase等人[64]僅利用OT、Hash函數(shù)、對稱密碼和位運算構建mOPRF，相比于文獻[63]基于多項式插值的OPRF更有效率，通過分析文獻[61]的協(xié)議構造可知無論發(fā)送方選擇不同s所得到的密鑰k，都有fk(y)=H(r0)，基于這一發(fā)現(xiàn)構建了1個新的mOPRF:新的OPRF密鑰包含一個大小為m×w的矩陣M.發(fā)送方選擇隨機字符串s∈{0,1}w，接收方準備2組列向量A1,A2,…,Aw∈{0,1}m，B1,B2,…,Bw∈{0,1}m.兩方執(zhí)行w個OT,發(fā)送方作為接收者得到w個列向量，由此得到OPRF密鑰M.接收方輸入元素y得到fM(y).發(fā)送方計算自身集合的fM(·)發(fā)送給接收方即可實現(xiàn)PSI協(xié)議.

Kavousi等人[70]采用星型-路徑(star-path)網(wǎng)絡結構并結合文獻[64]的mOPRF構造出半誠實多方PSI協(xié)議.star模塊用于指定方Pt作為發(fā)送方與其他所有參與者執(zhí)行OT，使得Pj(j∈[1,t-1])秘密共享Pt的矩陣并得到1個隨機字符串的列向量矩陣.path模塊用于重構秘密，即每一個參與方僅向最后參與方的方向的相鄰參與方發(fā)送混淆布隆過濾器(garbled Bloom filter, GBF)，一直持續(xù)到Pt-1，Pt-1計算GBF和OPRF值，并將OPRF值發(fā)送給指定方Pt，Pt通過比較OPRF值得到交集.這種設計使得每一方(指定方除外)的通信和計算復雜度僅取決于其自己的輸入集大小，而不取決于協(xié)議中涉及的參與方數(shù).

Hemenway等人[71]提出基于1-out-of-kHash和Silent-OT[23]構建OPRF實例.Silent-OT相較于IKNP-OT具有通信量顯著下降的特點.使用Silent-OT協(xié)議和1-out-of-kHash實現(xiàn)離線預處理階段計算其元素的最優(yōu)分配.1-out-of-kHash通過數(shù)組A表示集合S，對于hashk查找x只需檢查是否A[hi(x)]=x，其具有高效的空間利用率和恒定的查找時間.當雙方不需要動態(tài)插入元素時，多項選擇Hash比布谷鳥Hash具有更好的性能，即可以在本地計算最優(yōu)分配.

Pinkas等人[65]通過改進布谷鳥Hash算法(probe-and-XOR, PaXoS)并結合OOS-OT[66]實現(xiàn)了第1個基于布谷鳥Hash的惡意安全PSI協(xié)議.PaXoS是1個將n個二進制字符串映射到m個二進制字符串的隨機函數(shù)，由Hash映射到對應插槽值異或得到集合元素，以消除布谷鳥Hash構建惡意PSI時泄露發(fā)送方未在集合交集中的集合信息問題.同時PaXoS具有與GBF相同的漸進編碼和解碼，但計算速率卻比GBF快.該文主要通過OOS協(xié)議的同態(tài)性質(zhì)構建PSI協(xié)議.

Rindal 等人[67]基于Vector-OLE[24]和PaXoS[65]數(shù)據(jù)結構提出批量化的OPPRF(batch-OPPRF,B-OPPRF)新構造.基于Vector-OLE[24]的Silent-OT構造新的OPRF，具有O(n)的通信量和計算量非常高效，并且以很小的開銷可實現(xiàn)惡意安全性.基于PaXoS數(shù)據(jù)結構實現(xiàn)了新型可編程PRF，PaXoS具有編解碼高效，其只需O(1)時間復雜度計算.

3.2 不經(jīng)意多項式評估

Freedman等人[8]將元素比較問題轉(zhuǎn)化為多項式求根問題，通過乘法同態(tài)加密性質(zhì)實現(xiàn)PSI.參與方P1和P2分別擁有集合X1和X2.首先P2利用具有乘法同態(tài)屬性的方案生成密鑰對(PK,SK)，將集合X2的元素作為多項式的根構建|X2|階多項式Q(·)，加密多項式系數(shù)發(fā)送給P1.P1對集合X1中的元素打亂并選擇1個隨機值rj，利用同態(tài)加密方案計算rj×Q(xj)+xj并將其發(fā)送給P2.P2解密，如果z屬于X1∩X2，則對任意的r都有r×Q(z)+z=r×0+z=z.否則r.Q(z)+z是1個隨機值.如果多項式的階數(shù)較大，將導致同態(tài)加密的指數(shù)計算成本較高.

3.3 混淆電路

混淆電路可將任意函數(shù)轉(zhuǎn)化為布爾電路，故集合求交也可由電路構造.基于電路的PSI協(xié)議通常效率低下，但仍是研究的熱點，因其具有通用性，不必更改主電路只需添加子電路，即可實現(xiàn)基于求交的函數(shù)，比如交集基數(shù)等.基于電路的隱私集合求交最樸素的想法是利用與門對大小為n的2個集合進行n2次比較，但其完全由電路構造產(chǎn)生了很高的通信復雜度.電路計算的通信量由比較次數(shù)、元素大小以及電路安全參數(shù)決定.然而元素大小和電路安全參數(shù)都是給定的，所以設計計算交集的電路困難之處在于決定哪些元素需要進行比較.基于混淆電路構造PSI的論文進展如圖2所示：

Fig. 2 The progress of GC based PSI protocols圖2 基于GC的PSI協(xié)議進展

Huang等人[51]提出了3種基于混淆電路的相等性測試(private equality test, PET)以實現(xiàn)隱私求交功能.第1種位與協(xié)議:將集合通過二進制向量表示，然后通過與門進行逐位與操作即可完成相等性測試.第2種是元素直接比較.第3種排序比較亂序協(xié)議(sort compare shuffle, SCS)，雙方以特定方式本地排序集合輸入，通過不經(jīng)意合并排序網(wǎng)絡計算2個集合的并集排序列表.然后通過混淆電路進行相鄰元素比較得到集合匹配列表，其比較次數(shù)為O(nlogn).最后通過亂序網(wǎng)絡對其進行重新排序以保證匹配元素位置信息不被泄露.

Pinkas等人[43]使用GMW協(xié)議優(yōu)化了SCS電路協(xié)議，通過減少OT次數(shù)對協(xié)議的通信進行優(yōu)化.隨后他們[52]提出電路階段化的思想:通過置換Hash技術減少元素的存儲大小和降低比較次數(shù)，再應用電路進行隱私成員測試(private set membership, PSM)評估.具體協(xié)議為:參與方P0使用布谷Hash算法構建布谷Hash表T0，P1構造樸素Hash表T1.由Hash性質(zhì)可知，P0和P1集合中的相同元素一定在2個Hash表的同一行.再通過電路逐行進行隱私成員測試，由于各方須隱藏映射到桶中的元素個數(shù)，因此剩余位置需填充虛擬值，由此產(chǎn)生不必要的比較.該協(xié)議將比較次數(shù)從O(n2)下降到O(nlogn/log logn)(n為集合大小，logn由布谷Hash表性質(zhì)決定)且使電路的深度不再和集合大小相關.

Pinkas 等人[53]設計了一種2維布谷鳥Hash，將比較次數(shù)下降到O(n)使得布爾電路計算交集的開銷只需ω(n).2維布谷鳥Hash結構由2個表TL，TR和4個公共Hash函數(shù)HL0，HL1，HR0，HR1組成.P2使用布谷Hash算法插入到表TR中.P1通過HL0，HL1將元素插入TL，或通過HR0，HR1將元素插入TR，通過改進的布谷鳥插入算法實現(xiàn).即P2將其每個元素映射到每個表中的1個子表.P1將其每個元素映射到其中1個表的2個子表.確保P1和P2的交集元素被映射到同一個子表中.最后共同構建1個電路，對每個桶中雙方存儲的元素進行比較得到交集.

Ciampi等人[81]基于文獻[52]的階段化思想，進一步設計了一個結果秘密共享的PSM協(xié)議，最后電路只需要做相等性測試，以此減少電路尺寸.該協(xié)議基于不經(jīng)意圖跟蹤構建隱私成員測試協(xié)議為:發(fā)送方構造1個二叉樹，每個節(jié)點包含1個對稱密鑰.發(fā)送方輸入二叉樹，接收方輸入測試元素，雙方執(zhí)行1-out-of-2 OT.其允許接收方不經(jīng)意地遍歷樹，將成員測試結果秘密共享，最后通過電路等值比較得到交集.

Pinkas等人[54]設計了1個B-OPPRF協(xié)議以完成隱私成員測試，將結果輸入電路執(zhí)行相等性測試.通過布谷鳥Hash和樸素Hash將隱私集合求交問題簡化為h個隱私成員測試問題.當調(diào)用b個OPPRF實例時，桶中隱私元素個數(shù)不一致導致每個桶的編碼數(shù)量不同，但是其總的編碼數(shù)量是固定的，故設計了1個提供大小為N并進一步隱藏每個桶中編碼點數(shù)量的原語稱為B-OPPRF.通過B-OPPRF協(xié)議完成隱私成員測試:P1作為發(fā)送者，在1個包含b個OPPRF獨立實例的B-OPPRF實例中，在第j個OPPRF實例中將所有編程輸出設置為單個隨機值tj.然后P0評估第j個OPPRF的T0[j]，如果T0[j]=T1[j]則P0和P1持有相等值.最后通過電路比較Fk(x)，因此該電路只需要對每個桶進行1次比較計算.通過B-OPPRF將桶的比較次數(shù)從O(logn)減少到1，但OPPRF在創(chuàng)建提示時使用多項式插值，導致計算復雜度增加.Chandran等人[55]基于上述B-OPPRF設計了1個嚴格的RB-OPPRF.通過使用1個具有3個Hash函數(shù)的布谷鳥Hash結構取代多項式插值結構完成B-OPPRF操作，將每個桶的比較次數(shù)從O(logn)減少到3，同時只產(chǎn)生線性計算開銷.

3.4 布隆過濾器

布隆過濾器[84]是一種對集合進行編碼的數(shù)據(jù)結構，其利用若干獨立分布的Hash函數(shù)將集合中的每個元素映射到二進制數(shù)組中最終得到1個輕量級1維數(shù)組，是有效進行集合相等性測試的工具.未保護隱私的BF構造PSI思想為:參與方P1和P2分別擁有集合S1和S2，參與方P1依據(jù)hashk構造1維數(shù)組bf1，將bf1的所有位設置為0，對每個x∈S1，計算hashk(x)作為bf1的索引并將對應位設置為1.P2為元素y進行相等性測試，即hashk(y)對應的bf1均為1，則y屬于S1.BF存在一定的錯誤率，其與Hash個數(shù)、BF長度、集合大小有關.文獻[85]對其進行詳細的分析并給出最佳BF構造參數(shù).基于布隆過濾器構造PSI協(xié)議進展如圖3所示.

Fig. 3 The progress of BF based PSI protocols圖3 基于BF的PSI協(xié)議進展

Dong等人[57]首先通過BF構建PSI:雙方根據(jù)其私有集構造BF.雙方執(zhí)行OT協(xié)議，P2獲得P1中BF為1的索引.最后P2通過計算2個BF上的逐位與操作，得到交集結果.但其泄露了P1的BF中為1但不屬于交集的額外信息.由此進而提出混淆布隆過濾器GBF，將元素x首先拆分為k個共享值并通過hashk映射得到k個BF索引，并將k個共享值隨機填充，將BF中的每1比特信息改為1個隨機字符串.GBF插入元素x步驟:計算hashk，共用GBF中已有字符串，剩下的位置通過異或得到共享字符串并填充入對應位置.基于GBF的隱私集合交集:P2根據(jù)私有集合構造BF，P1根據(jù)私有集合構造gbf1和隨機填充gbf2.P2測試元素x是否屬于P1的私有集合執(zhí)行為:雙方執(zhí)行m個1-out-of-2 OT(m為BF長度)，P1輸入消息對(gbf1,gbf2)，P2輸入BF作為選擇位，P2只能獲得gbf[hi(x)]，i∈[1,k].然后P2將k個gbf[hi(x)]進行重組與x比較即可完成測試.

Rindal等人[58]通過生成比所需的BF比特數(shù)略多的1-out-of-2 OT構建Cut-and-Choose技術以此實現(xiàn)抵抗惡意敵手的PSI協(xié)議:P1從OT中隨機抽取一小部分，讓P2證明適當數(shù)量的OT中使用了選擇位0.然后再進入在線階段，執(zhí)行離線階段未使用的OT協(xié)議.

Pinkas等人[43]基于隨機OT擴展設計了1個不經(jīng)意偽隨機發(fā)生器(oblivious pseudo random generator, OPRG)以完成GBF的構建:雙方基于私有集構建BF,分別為bfx和bfy，將bfx和bfy的每一個對應比特bx,by作為OPRG的輸入.OPRG產(chǎn)生1個隨機字符串發(fā)送給bt=1(t∈{x,y})的參與方構建出gbfx和gbfy.對集合X的每一個元素xi，P1計算m1[i]=gbfx[h1(xi)]⊕gbfx[h2(xi)]⊕…⊕gbfx[hk(xi)].P1將m1打亂并發(fā)送給P2，P2通過檢查是否存在1個i使得m1[i]=gbfy[h1(yi)]⊕gbfy[h2(xi)]⊕…⊕gbfy[hk(yi)]判斷元素yi是否為交集.相比于GBF，OPRG具有更小的通信量和計算量.

Inbar等人[68]通過秘密共享將文獻[57]擴展為多方PSI協(xié)議:每個參與方Pi通過hashk本地生成GBF和BF.然后參與方Pi選擇t個隨機字符串共享GBF，將字符串分發(fā)給其他參與方，以完成在所有各方之間(t,t)異或秘密共享其GBF.Pi將其接收到的所有GBF的共享字符串異或后，得到新的GBF再將其發(fā)送給P0.P0對所有的GBF進行異或再和本地BF異或得到交集.Zhang等人[59]使用星型拓撲結構[46]和Cut-and-Choose[58]技術實現(xiàn)多方惡意安全的PSI.協(xié)議通過離線-在線階段的方式進一步優(yōu)化，將多數(shù)繁重的計算、通信放在預計算階段.

Karako?等人[69]繼承文獻[54]的設計思想，通過布谷鳥Hash算法構建2維表，再對每個桶運行PSM協(xié)議，執(zhí)行比較協(xié)議并完成具有可計算對稱函數(shù)的電路PSI.文獻[68]通過修改文獻[57]的結構，設計了基于BF的PSM:顯著降低了通信量，且不再使用電路進行等值比較，而是將PSM通過控制參與方只輸入1個元素得到PET，執(zhí)行PET使得等值測試不消耗任何通信量.

Efraim等人[60]改進了惡意安全的兩方PSI協(xié)議[58]結合半誠實安全的多方PSI協(xié)議[68]構造出高效的惡意安全的多方PSI協(xié)議.首先為解決直接結合協(xié)議造成通信量隨參與方數(shù)量的增加而指數(shù)增長的問題對惡意兩方協(xié)議[58]進行了改進:通過P2和P1執(zhí)行k-out-of-NOT，使得P2獲得P1的GBFG1的適當部分.然后引入重隨機化GBF的概念，P2重隨機化GBF得到reGBF.雙方再次執(zhí)行k-out-of-NOT，其中P2和P1角色互換，讓P1獲得P2的reGBF適當部分，該過程避免了直接發(fā)送GBF而泄露P1不在交集的元素信息.最后P2通過比較reGBF和自身GBF得到隱私集合交集.為將兩方協(xié)議推廣到多方協(xié)議，首先讓P0與每一方Pi執(zhí)行2次k-out-of-NOT協(xié)議，OT執(zhí)行之前先執(zhí)行Cut-and-Choose技術以抵抗惡意敵手，然后P0將其得到的所有GBF進行異或操作得到GBFG0.同時Pi與P0交互得到的GBF和自身GBF異或得到Gi.最后為克服Pi直接將Gi發(fā)送給P0使得P0可以獲得與每一方的交集問題，所有參與方需執(zhí)行t-t秘密共享Gi，并將得到的份額求和再發(fā)給P0，求得多方交集.

4 新型場景的隱私集合交集

4.1 非平衡PSI

傳統(tǒng)PSI的大部分方案往往要求參與方集合的大小相等或相近，并且假設了雙方具有相似的計算和存儲能力，稱之為平衡PSI.然而，在某些實際應用中，如隱私聯(lián)系人發(fā)現(xiàn)，客戶擁有幾百到幾千個聯(lián)系人集合，而服務方擁有百萬甚至千萬級的用戶集合，它們的集合大小不平衡，技術能力和存儲空間也相差甚遠.使用平衡PSI協(xié)議，它們的通信開銷和計算開銷均與較大集合成線性關系，導致客戶端需承受巨大的存儲與計算開銷.這激發(fā)了對不平衡PSI的研究.

目前，只有少數(shù)研究考慮了集合大小不對稱的情況:Chen等人[86]使用同態(tài)加密將大小為N的集合的通信量減少到O(logN).接收方加密集合并將其發(fā)送給發(fā)送方，發(fā)送方通過計算適當?shù)谋容^電路來計算同態(tài)加密數(shù)據(jù)的交集.使用同態(tài)乘法將輸出壓縮到更小的尺寸，并發(fā)送回接收方進行解密.在協(xié)議中，接收方只執(zhí)行相對較輕的計算，當接收方的計算能力有限時(如移動設備)，該協(xié)議十分有效.在此基礎上，Chen等人[87]使用OPRF預處理階段來實現(xiàn)比文獻[86]更高的性能和安全性，實現(xiàn)了針對惡意客戶端和惡意服務器的安全性，并將集合求交擴展到帶標簽PSI的特殊用例，其對于相交元素傳輸相關聯(lián)的標簽.協(xié)議的優(yōu)點是它們的通信復雜度是次線性的，而不是服務器集合大小的線性，然而，協(xié)議的缺點是以重復的高計算開銷作為代價.

Kiss等人[88]描述了一種將O(N)通信量放在預處理階段的方法，其中服務器為每個元素x發(fā)送包含AES(k,x)的大型Bloom過濾器.各方使用Yao協(xié)議來對客戶端的每個元素上的AES進行模糊評估，客戶端可測試Bloom過濾器的成員資格.即服務器只能對其數(shù)據(jù)執(zhí)行1次操作，并將結果發(fā)送給客戶端，客戶端將在未來的執(zhí)行中使用它們來計算交集.Resende等人[89]設計了一個更節(jié)省空間的布谷鳥過濾器用于服務器預處理階段發(fā)送大消息，以節(jié)省存儲和通信成本.為了進一步減少通信，發(fā)送方將集合X轉(zhuǎn)發(fā)給接收方之前對其進行壓縮.雖然這種壓縮確實減少了通信，但在高壓縮率下產(chǎn)生誤報，接收方以不可忽略的概率輸出YX中的元素.

Resende等人[90]通過基于排名和選擇的商過濾器(rank and select based quotient filter, RSQF)來減少協(xié)議交換的數(shù)據(jù)量，相比其他數(shù)據(jù)結構具有更小的存儲空間，支持刪除、插入、查找、合并等操作，當集合達到最大容量時可重構過濾器，而無需從頭開始生成新的過濾器，在隱私聯(lián)系人查找等應用場景具有重要意義.文獻[90]將RSQF數(shù)據(jù)結構引入PSI協(xié)議中，通過放寬常數(shù)時間執(zhí)行加速橢圓曲線提高協(xié)議計算性能.離線階段，服務器對元素使用插入操作生成RSQF，并將RSQF發(fā)送給客戶端.在線階段，客戶端和服務端進行交互以掩蓋客戶端元素，客戶端通過查找操作判斷它的元素是否屬于RSQF，從而得到集合的交集.

在最近的研究中，Lv等人[91]研究了在不平衡場景下計算集合交集的基數(shù)，利用Bloom過濾器構造低通信復雜度計算非平衡私有集合交集基數(shù).接收方不需要用低功耗設備加密發(fā)送方的數(shù)據(jù)集，當接收方的數(shù)據(jù)集比發(fā)送方的數(shù)據(jù)集小得多時，協(xié)議實現(xiàn)了高效率.

4.2 云輔助PSI

隨著云技術的發(fā)展，基于云服務器的PSI協(xié)議逐漸成為熱點.云服務器具有高計算能力和存儲容量，為現(xiàn)有的PSI協(xié)議提供了成熟的優(yōu)化方法，但又產(chǎn)生了數(shù)據(jù)外包的隱私泄露問題.基于云輔助的PSI協(xié)議可分為數(shù)據(jù)加密和數(shù)據(jù)盲化2種.

Kerschbaum[92]提出服務器代理其中一個客戶端A與另一個客戶端B利用單向函數(shù)實現(xiàn)PSI操作，且代理是一次性.之后，Kerschbaum[93]提出將2個客戶端的BF通過同態(tài)加密外包給云服務器而不是對數(shù)據(jù)本身加密外包給服務器，服務器進行PSI操作.客戶端只需本地保留集合元素以驗證得到的交集BF里包含的本地元素.Liu等人[94]直接利用對稱和非對稱加密方案對數(shù)據(jù)集加密并外包給云服務器，云服務器每進行一次PSI操作時，客戶端都需下載加密向量，且會向服務器泄露交集基數(shù).Kamara等人[95]基于偽隨機密鑰對集合元素進行盲化處理再發(fā)送給云服務器，但交集計算任務仍在客戶端中進行，服務器只為某一個客戶端重新編碼集合來維護計算隱私性.Qiu等人[96]將隱私集合求交計算完全委托給服務器，但需要確保服務器可信，因為云服務器可不經(jīng)客戶端同意進行PSI計算并得到交集基數(shù).以上基于云服務器的PSI協(xié)議并不能完成云服務器的理想功能，如數(shù)據(jù)集仍需本地存儲、數(shù)據(jù)需反復上傳下載、PSI計算不能完全委托給云服務器等.

Abadi等人[47]提出O-PSI，利用點值多項式和Paillier同態(tài)加密實現(xiàn)將隱私集合求交操作完全委托給服務器，無需本地維護集合，客戶只需上傳1次外包數(shù)據(jù)集即可應用到多次隱私集合交集計算的理想云服務器功能，但是其方案基于公鑰密碼操作，過于昂貴.Abadi 等人[97]提出基于Hash表和點值多項式表示集合構造了一種即具有云服務器理想功能又無需公鑰操作的高效PSI方案，稱為EO-PSI.但各方之間需事先建立安全通道，否則攻擊者可以竊聽隱私信息.Kavousi 等人[98]提出無需安全通道的改進協(xié)議.O-PSI理想云服務器功能構造為:客戶端A，B為偽隨機函數(shù)選取隨機密鑰k.構造多項式點值對{(x1,y1),(x2,y2),…,(xn,yn)}表示集合，將由yi組成的向量Y=(y1,y2,…,yn)通過隨機值ri=f(k,i)進行盲化，得到向量v=(y1r1,y2r2,…,ynrn)發(fā)送給服務端.客戶端若同意云服務器計算交集，則客戶端B使用Paillier加密盲化值，發(fā)送給客戶端A，A再對其加密發(fā)生給服務器.最后服務器利用加法同態(tài)性質(zhì)進行PSI操作得到向量T將其發(fā)送給客戶端B，客戶端利用私鑰解密得到由yi(A)和yi(B)組成的zi，最后通過點值對(xi,zi)進行多項式插值得到交集元素.

李順東等人[99]在云計算環(huán)境下設計了多方隱私集合求并(求交)方案.通過輸入集合域已知的1-r編碼(0-r編碼)將求并(求交)集合表示為向量，借助哥德爾編碼將向量編碼為自然數(shù)x，利用同態(tài)加密得到密文E(x)以防止泄露明文，利用模運算對密文進行秘密共享以防止云服務器合謀，利用模運算性質(zhì)對所有密文相乘再通過算術基本定理展開得到并(交)集集合，但方案限制了輸入集合的范圍以及不能進行兩方計算.

Abadi等人[100]提出支持外包數(shù)據(jù)集有效更新和可擴展的多方隱私集合求交協(xié)議Feather，允許客戶端只上傳1次私有數(shù)據(jù)集即可無限次委托計算，無需公鑰密碼操作使其具有高效率和高可伸縮性.協(xié)議由3部分組成：1)設置階段.客戶端構造Hash表并為每個桶生成1個多項式、BF和標簽，利用偽隨機函數(shù)盲化BF，并隨機排列桶、盲化BF和標簽.客戶端保留標簽到桶的映射和排列，向云發(fā)送置換的桶、BF和標簽.2)更新階段.客戶端利用Hash函數(shù)確定更改集合元素所在桶，計算桶的標簽將其發(fā)送給云，云將標簽對應的桶和盲化BF發(fā)送給客戶端，客戶端利用密鑰恢復桶的內(nèi)容對其進行重新編碼然后將更新的桶和過濾器發(fā)送給云服務器.3)PSI計算階段是基于文獻[97]的改進.

Debnath等人[101]利用BF、乘法同態(tài)加密、零知識證明-數(shù)據(jù)簽名結合技術設計了一種抵抗惡意敵手的O-PSI結構.協(xié)議實現(xiàn)了標準模型安全且取得了較低的線性復雜度.協(xié)議包括1組客戶端{C1，C2,…,Cn}和1個云服務器S.如果客戶端Ci想要學習和Cj的交集.Ci通過簽名消息對請求Cj許可，如Cj許可則將簽名消息對發(fā)送給S.S計算結果集并將結果集和從Cj收到的簽名消息對發(fā)送給Ci.最后Ci在本地計算交集結果.

Ali等人[102]基于屬性基加密的思想提出屬性基私有集合求交 (AB-PSI) 方案，可提供細粒度的訪問控制，并允許數(shù)據(jù)擁有者通過定義訪問控制策略控制其外包數(shù)據(jù)集的訪問權限，實現(xiàn)數(shù)據(jù)擁有者不參與的情況下完成PSI操作，云服務器通過隱私集合交集訪問權限和盲化后數(shù)據(jù)集計算出相應的訪問權限.如果請求交集的客戶端能得到一個有效的訪問權限，則可計算出其數(shù)據(jù)集和請求數(shù)據(jù)集的交集.Shi等人[103]基于密鑰策略屬性加密(key-policy attribute-based encryption, KP-ABE)和PSI相結合提出一個新的概念:基于委托密鑰策略屬性的外包加密數(shù)據(jù)集交集(KP-ABPSI)，以實現(xiàn)隱私集合交集計算完全委托給云服務器和對PSI的細粒度訪問控制.集合元素d被加密為2部分：第1部分和元素d本身相關，進行加密盲化；第2部分和訪問控制策略相對應的屬性集相關.數(shù)據(jù)用戶生成與第2部分相關的令牌，一旦令牌滿足訪問控制權限，云服務器就能得到d被加密的第1部分，最后進行PSI操作將結果返回給數(shù)據(jù)用戶，數(shù)據(jù)用戶對其解密得到交集元素.

4.3 閾值PSI

閾值PSI指當交集的基數(shù)大于或等于門限值時，接收方才能獲得隱私集合交集.如網(wǎng)約順風車，在不泄露陌生人路徑的情況下如何共享雙方的公共路徑是該場景的重點問題.

Hallgren等人[104]通過構造門限密鑰封裝機制，實現(xiàn)交集的基數(shù)與閾值隱私比較，從而得到TPSI. Zhao等人[105]基于不經(jīng)意多項式評估構建了1個加密私有集合交集基數(shù)(ePSI-CA)協(xié)議，通過外包擴展使協(xié)議更接近于現(xiàn)實世界的模型.以上TPSI協(xié)議首先計算交集基數(shù)，再比較其與閾值t的關系考慮是否執(zhí)行PSI協(xié)議，其通信復雜度依賴于集合的大小.

Ghosh等人[106]提出了第1個通信復雜度僅依賴門限t的PSI協(xié)議，其通過測試兩集合是否足夠相似而非計算交集基數(shù).其基于較弱假設，計算效率高但通信復雜度為O(t2)，具體思想為：雙方將集合各自編碼為多項式，將兩多項式相除，消掉相同項得到階數(shù)更低的有理函數(shù)，通過比較有理函數(shù)階數(shù)和閾值來判斷是否執(zhí)行PSI協(xié)議.Badrinarayanan等人[107]設計了2種多方TPSI協(xié)議，其通信復雜度隨集合差的增大而增加，當集合差值明顯小于集合大小時，該協(xié)議具有次線性通信復雜度.Branco等人[108]基于門限加法同態(tài)加密方案提出了一種新的允許N方檢查其輸入集的交集是否大于N-t的TPSI方案，該協(xié)議通信復雜度為O(NT2).

Mahdavi等人[109]介紹了另一種TPSI場景:多方分別持有1個集合，希望了解哪些元素至少出現(xiàn)在t個集合中，而其他信息不被泄露，稱為超閾值多方PSI(OT-MP-PSI)，通過構造不經(jīng)意偽隨機秘密共享(oblivious pseudo-random secret sharing, OPR-SS)實現(xiàn)OT-MP-PSI協(xié)議，其通信復雜度為O(nmk).共享階段:密鑰持有方持有密鑰k和值S，以及一組參與者Pi持有輸入集合Si.每個參與方Pi輸入Si和隨機值ri，得到共享集合.由于具有OPRF的安全性，保證參與方Pi不知道密鑰k，密鑰持有者不知道集合Si.重構階段:參與方將共享集合構建為Hash表并發(fā)送給重建者，重建者對所有的參與方選擇t個執(zhí)行拉格朗日插值驗證每一行的元素是否大于等于閾值t，然后將其發(fā)送給參與方.此過程重建者無法知道元素S(i)，但參與方可以知道自己的哪些集合元素至少出現(xiàn)在其他t-1個集合中.

Zhang等人[110]基于GBF和秘密共享構建了一個新的TPSI，其通信復雜度為O(λm)，通過設計一種新的GBF來建立集合元素和秘密共享之間的關系，并使用其作為TPSI的門限檢測，并通過秘密關系方案確定|X∩Y|和門限t的關系，只有當交集中有足夠的元素時接收者才能重構秘密共享方案的多項式以獲得交集.結合Reed-Solomon編碼算法改進了秘密共享的重構階段，通過忽略錯誤的共享而避免計算所有可能的共享組合重構秘密的可行方法.

4.4 多方PSI

隱私集合交集目前存在的高效協(xié)議大多只針對兩方設置，多方PSI的高效協(xié)議并沒有引起多大關注.這可能與各方之間不可避免的通信而導致極大的通信成本有關.目前關于多方設置的PSI協(xié)議大多采用2種網(wǎng)絡模型:1)星型拓撲網(wǎng)絡結構減少雙方之間的中間交流，但給指定方帶來了很高的工作量.2)星型-路徑網(wǎng)絡結構其使每一方(除指定方)的通信量和計算復雜度僅取決于自身輸入集大小.還可能與如何保證只能獲得所有參與方的集合交集，而不能獲得部分參與方的集合交集有關.目前多方PSI協(xié)議主要通過秘密共享解決該問題，使得只能秘密重構交集元素.Kolesnikov等人[62]通過指定方與各方執(zhí)行OPPRF協(xié)議實現(xiàn)交集元素的零共享，Hazay等人[46]通過構造門限同態(tài)加密方案實現(xiàn)元素的零共享.零共享指如果所有各方都持有相同的值x，共享異或得到0，否則得到1個隨機值. Inbar等人[68]、Efraim等人[60]利用GBF和OT實現(xiàn)元素秘密共享.Kavousi等人[70]不再對集合元素進行秘密共享而是對密鑰進行秘密共享，通過路徑結構，逐一得到由密鑰k加密的OPRF值，指定方對OPRF值進行比較得到交集結果.為了對上述提到的多方協(xié)議性能有更加深刻的認識，從通信量(指定方，其他方)、計算量、安全模型、設計思想及隱藏技術、網(wǎng)絡結構等方面總結如表3所示:

Table 3 Complexity Analysis for Multiparty PSI表3 多方PSI復雜性分析

5 總 結

綜上所述，隨著安全多方技術研究的逐步深入，PSI作為安全多方計算的一種重要應用，已被廣泛應用于隱私計算，具有重要的理論和實踐意義.首先介紹PSI協(xié)議的密碼技術、敵手模型、安全證明、編程框架，其次系統(tǒng)總結了傳統(tǒng)PSI協(xié)議的密碼框架，隨后介紹PSI協(xié)議中集合元素比較技術，進一步地詳細闡述了適應新型應用場景的PSI方案.隨著密態(tài)數(shù)據(jù)的隱私計算技術進一步深入，傳統(tǒng)的PSI在安全性、高效性、適用性、可擴展性等方面受到了巨大的挑戰(zhàn).因此，未來的主要研究方向建議在4個方面:

1) 考慮威脅性更高的場景，設計不同安全性需求的PSI協(xié)議.在目前主流PSI協(xié)議設計中，通常只考慮半誠實的敵手.然而在協(xié)議執(zhí)行過程中可能會有黑客等侵入、篡改甚至偽造數(shù)據(jù)，因此需將半誠實模型推廣到惡意模型，協(xié)議需要保證在惡意攻擊下仍然使得數(shù)據(jù)具有一致性與可用性.

2) 考慮更多的參與方，從而增加適用范圍.傳統(tǒng)的PSI協(xié)議一般只有2個參與方(即發(fā)送方和接收方)，而兩方PSI協(xié)議所使用的技術在一般無法簡單推廣至構建多方PSI協(xié)議，且會導致部分隱私數(shù)據(jù)的泄露，多方PSI協(xié)議允許多個參與方共同計算所有參與方的交集，這使得問題的難度進行了提升，也增加了PSI協(xié)議的適用范圍.

3) 面向新型場景構建PSI協(xié)議.在某些特定場景中，通過PSI協(xié)議得到的交集元素仍然是敏感信息，如電子醫(yī)療中的病患數(shù)據(jù)、基因測序中的序列數(shù)據(jù)等，需要對現(xiàn)有PSI協(xié)議進行改造，允許參與方在交集保密的情況下對交集中的元素進行各種函數(shù)的運算，如計數(shù)、求和等.

4) 提高現(xiàn)有方案的效率.目前大部分的PSI方案都是復雜的密碼學操作，如基于全同態(tài)加密、不經(jīng)意傳輸、混淆電路、公鑰加密等，計算或通信開銷隨數(shù)據(jù)集大小呈現(xiàn)線性增長.目前PSI協(xié)議在百萬數(shù)據(jù)集下的運算速度尚能接受，但當數(shù)據(jù)集大小達到百億數(shù)量級時，傳統(tǒng)的PSI方案效率會大幅度下降，迫切需要構建面向海量數(shù)據(jù)的高效PSI協(xié)議，實現(xiàn)數(shù)據(jù)的共享.