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

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

　　關鍵詞 隱私集合求交; 安全多方計算; 隱私保護; 不經意傳輸; 混淆電路

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

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

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

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

　　1 定義與基礎知識

　　1.1 基礎協議

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

　　1.2 敵手模型

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

　　1.3 安全性證明方法

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

　　1.4 編程框架

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

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

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

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

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

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

　　2.3 基于不經意傳輸的設計框架

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

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

　　3.1 不經意偽隨機函數

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