魏立斐 劉紀(jì)海 張 蕾 王 勤 賀崇德

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

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

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

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

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

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

1 基礎(chǔ)知識(shí)

1.1 密碼技術(shù)

1.1.1 秘密共享

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

1.1.2 同態(tài)加密

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

1.1.3 不經(jīng)意傳輸

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

1.1.4 混淆電路

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

1.1.5 Hash技術(shù)

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

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

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

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

1.2 敵手模型

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

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

1.3 安全性證明方法

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

1.4 編程框架

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

Table 1 MPC Framework Comparison表1 MPC框架對(duì)比

2 隱私集合交集的設(shè)計(jì)框架

2.1 基于公鑰加密的設(shè)計(jì)框架

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

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

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

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

2.2 基于混淆電路的設(shè)計(jì)框架

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

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

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

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

3 隱私集合元素比較技術(shù)/工具

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

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

Fig. 1 The progress of OPRF based PSI protocols圖1 基于OPRF的PSI論文進(jìn)展

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

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

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

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

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

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

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

3.2 不經(jīng)意多項(xiàng)式評(píng)估

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

3.3 混淆電路

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

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

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

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

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

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

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

3.4 布隆過濾器

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

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

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

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

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

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

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

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

4 新型場(chǎng)景的隱私集合交集

4.1 非平衡PSI

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

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

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

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

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

4.2 云輔助PSI

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

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

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

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

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

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

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

4.3 閾值PSI

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

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

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

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

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

4.4 多方PSI

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

Table 3 Complexity Analysis for Multiparty PSI表3 多方PSI復(fù)雜性分析

5 總 結(jié)

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

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

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

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

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