面向隱私保護的集合交集計算綜述

　　摘要 隨著物聯(lián)網(wǎng)和大數(shù)據(jù)技術(shù)的發(fā)展, 在計算機和手機上出現(xiàn)了大量分布式應(yīng)用程序. 然而現(xiàn)有的分布式數(shù)據(jù)處理方式已不能很好地滿足用戶對隱私保護的需求. 隱私集合交集計算(private set intersection, PSI)協(xié)議作為一項典型的面向隱私保護的分布式集合計算技術(shù), 允許各參與方輸入其私有集合, 共同計算集合的交集, 且不泄露除交集以外的任何信息. PSI 協(xié)議作為安全多方計算的一種重要應(yīng)用, 已被廣泛應(yīng)用于隱私計算領(lǐng)域, 具有重要的理論和實踐意義. 首先介紹 PSI 協(xié)議的基本密碼技術(shù)、敵手模型、安全證明、編程框架等基礎(chǔ)知識;其次系統(tǒng)總結(jié)了構(gòu)造傳統(tǒng) PSI 協(xié)議的設(shè)計框架: 基于公鑰加密體制的框架、基于混淆電路的框架、基于不經(jīng)意傳輸?shù)目蚣?隨后介紹 PSI 協(xié)議核心的隱私集合元素比較技術(shù)/工具: 不經(jīng)意偽隨機函數(shù)、不經(jīng)意多項式評估、布隆過濾器等;進一步地詳細闡述了適應(yīng)新型應(yīng)用場景的 PSI 方案: 基于云輔助的 PSI、非平衡型 PSI、基于閾值的 PSI 和多方 PSI;最后總結(jié)并展望面向隱私保護的集合交集計算中亟待解決問題和發(fā)展方向.

　　關(guān)鍵詞 隱私集合求交; 安全多方計算; 隱私保護; 不經(jīng)意傳輸; 混淆電路

　　魏立斐; 劉紀海; 張蕾; 王勤; 賀崇德， 計算機研究與發(fā)展 發(fā)表時間：2021-11-18

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

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

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

　　1 定義與基礎(chǔ)知識

　　1.1 基礎(chǔ)協(xié)議

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

　　1.2 敵手模型

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

　　1.3 安全性證明方法

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

　　1.4 編程框架

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

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

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

　　隱私集合求交早期思想直接對元素進行加密, 然后在密文上進行相應(yīng)的比較操作. 其最常用的技術(shù)是同態(tài)加密, 發(fā)送方加密集合發(fā)送給接收方. 接收方利用同態(tài)加密的性質(zhì)對密文進行計算, 并將計算結(jié)果發(fā)給發(fā)送方, 發(fā)送方利用私鑰對其解密并得到集合交集. 基于公鑰加密的安全性假設(shè)主要分為 3 類: 1) 基于 DH(Diffie-Hellman) 假設(shè). Meadows [6]基于離散對數(shù)困難問題實現(xiàn) DH 密鑰交換協(xié)議并以此實現(xiàn) PSI 功能, Huberman 等人[7]發(fā)現(xiàn)基于橢圓曲線密碼的 PSI 相較于基于離散對數(shù)密碼的 PSI 具有更高的安全性和高效性. 2) 基于 RSA 假設(shè). Cristofaro 等人[42]基于整數(shù)分解困難問題的 RSA 盲簽名技術(shù)實現(xiàn)半誠實 PSI 協(xié)議, 文獻[43]分析基于離散對數(shù)密碼的 PSI 協(xié)議比基于整數(shù)分解密碼的 PSI 協(xié)議更加高效. 3) 基于同態(tài)加密. Freedman 等人[8]將元素表示為多項式的根, 利用 Paillier 同態(tài)加密技術(shù)加密多項式系數(shù)和零知識證明實現(xiàn)兩方惡意攻擊安全的 PSI 協(xié)議, 2016 年 Freedman 等人[44]使用 ElGamal 加密加快計算效率和布谷鳥 Hash 技術(shù)降低計算復(fù)雜度. Kissner 等人[45] 采用不同的多項式表示方法將計算開銷下降到與參與人數(shù)呈線性關(guān)系. Hazay 等人[46]構(gòu)建一個具有門限解密的加法同態(tài)加密方案實現(xiàn)多方半誠實 PSI 協(xié)議 . Abadi 等人[47]提出基于點-值對的 d 次多項式表示集合方法, 通過 Paillier 加密方案完成, 將乘法復(fù)雜度從 O(d 2 )下降到 O(d). Jarecki 等人[48]使用加法同態(tài)加密和零知識證明來實現(xiàn)偽隨機函數(shù)(pseudo-random function, PRF). Dou 等人[49]基于有理數(shù)編碼和三角形面積計算公式并結(jié)合 Paillier 加密實現(xiàn)有理數(shù)上的 PSI 協(xié)議. 基于公鑰加密的 PSI 協(xié)議一般具有較小的通信輪數(shù), 適用于具有較強計算能力的模型, 但通信帶寬和時間復(fù)雜度是實際應(yīng)用中一個很大的瓶頸障礙.

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

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

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

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

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

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

　　利用 OPRF 設(shè)計 PSI 協(xié)議是一種常見的思想. OPRF 允許接收方輸入