作者：京東科技 孫曉軍

摘要

隱私集合求交（PSI）是安全多方計算（MPC）中的一種密碼學技術，它允許參與計算的雙方，在不獲取對方額外資訊（除交集外的其它資訊）的基礎上，計算出雙方資料的交集。隱私集合求交在資料共享，廣告轉化率，聯絡人發現等領域有著廣泛的應用空間。本文對隱私集合求交的各項實現技術做了介紹和對比，對隱私集合求交的原理進行了分析，並進一步闡述了隱私集合求交目前面臨的挑戰和發展前景。

【關鍵詞】：隱私集合求交，安全多方計算，不經意傳輸

1 引言

隱私集合求交（PSI）是安全多方計算（MPC）中的一種密碼學技術，它允許參與計算的雙方，在不獲取對方額外資訊（除交集外的其它資訊）的基礎上，計算出雙方資料的交集。隨著大資料，人工智慧，雲端計算等技術的興起，企業和個人對隱私資料的保護越來越重視。隱私集合求交，作為安全多方計算中的關鍵技術，在近年來的理論研究也得到了長足的發展。

在數字經濟的眾多安全威脅中，資料洩露已成為全球範圍高發的安全事件之一，且這個趨勢仍在持續。

• 2018年，Facebook因向第三方公司惡意洩露其使用者資訊被判罰數十億美元
• 2019年，位元組跳動因收集未成年人資訊被罰款總計約1億美元
• 2020年，中國電信2億使用者資訊被販賣，相關人員被判刑並處以罰款
• 2021年，亞馬遜因違反資料隱私法規被處罰8.88億美元

在這些資料安全問題中，有人為原因的故意洩露，也有技術缺陷導致的資料洩露。資料隱私問題，直接影響著企業的利益和信用，甚至因此導致企業倒閉。

隨著中國在資訊化和數字化的持續發展，大量具有敏感性和私密性的個人和企業資訊在網際網路上傳播。如何安全地利用這些資訊為企業和個人提供便捷的服務，同時又能保障資訊不在傳輸過程中被洩露，對數字經濟的健康發展，有著非常重要的作用和意義。
2021年6月10日，十三屆人大常委會第二十九次會議通過了《資料安全法》
2021年8月20日，十三屆人大常委會第三十次會議表決通過《中華人民共和國個人資訊保護法》。
可以預見，對個人和企業隱私資料的保護，會被越來越多的企業和個人重視。我們通過對隱私集合求交的現狀和發展的綜述，重點介紹隱私集合求交的技術原理，為建立企業和個人對隱私資料保護的重視和信任，提供理論依據，並對隱私集合求交的發展前景進行分析，推進隱私計算的基礎研究和商業應用發展。

2 基礎原語

2.1 安全模型

安全模型又被稱為對手模型或敵手模型，被用來衡量一個協議的安全等級。基於模型的安全假設，通常把安全模型分為誠實（honest），半誠實（semi-honest）和惡意（malicious）三種。

• 誠實型對手會完全按照密碼學的協議執行，並且不會主動嘗試獲取額外的資訊。
• 半誠實型對手會完全按照密碼學的協議執行，但會盡可能嘗試從收到的資訊中獲取額外的資訊。
• 惡意模型不會嚴格按協議執行，他們可以做任何事情來達到獲取額外資訊的目的。

迄今為止，隱私集合求交的協議，大多基於對手模型是半誠實模型的前提下進行的研究。對抗惡意模型的協議，雖然提供了更好的安全保障，但通常具有較為低下的執行效率[8]。雖然半誠實模型不能對協議的雙方提供完全的安全保護，但基於半誠實模型的協議的研究，可以為對抗惡意模型的協議，提供技術儲備。並且基於對手模型為半誠實模型的協議，可以通過配合諸如隨機預言，懲罰性措施等多種技術手段，來達到接近惡意模型下的協議的效果。

2.2 祕密共享

祕密共享（Secret Sharing，SS）是將一份原始祕密資訊，拆分成多份。再把多份資料，分給不同的使用者持有。其中的任何一份資料，都不能夠完全恢復原始的祕密資訊。只有達到指定數量的使用者，集合他們手中持有的祕密，經過計算才能得出原始的祕密資訊。祕密共享的關鍵在於祕密的拆分方式和恢復方法。祕密共享已經成為密碼學中的一個重要分支，是資訊保安和資料保密中的重要手段，被廣泛應用於電子支付，金鑰託管和隱私保護領域。

2.3 同態加密

同態加密（Homomorphic Encryption，HE）是將資料加密後，對加密資料進行運算處理，之後對資料進行解密，解密結果等同於資料未進行加密，並進行同樣的運算處理。目前，同態加密支援的運算主要為加法運算和乘法運算。按照其支援的運算程度，同態機密分為半同態加密（Partially Homomorphic Encryption, PHE）和全同態加密（Fully Homomorphic Encryption, FHE）。半同態加密在資料加密後只持加法運算或乘法運算中的一種，根據其支援的運算的不同，又稱為加法同態加密或乘法同態加密。半同態加密由於機制相對簡單，相對於全同態加密技術，擁有著更好的效能。全同態加密對加密後的資料支援任意次數的加法和乘法運算。

3 隱私集合求交的主要技術方案

3.1 樸素雜湊求交技術

樸素雜湊（simple hashing）求交技術[1]的原理是使用雜湊函式，把集合中的元素對映到一個均勻分佈的空間。利用雜湊函式的不可逆的性質，傳輸對映後的資料並進行比對求交。

樸素雜湊求交法是一種非安全的求交方法。如果傳送者Alice持有的資料集X的樣本空間Ω較小（比如手機號碼或特定的電子郵件等），那麼Bob在接收資料後，可以進行對樣本空間內的所有資料進行雜湊計算來破解。即使要比對的資料擁有足夠大的樣本空間，樸素雜湊求交法也並非絕對安全，接收者Bob仍可以根據獲取到的計算後的資料，判斷Alice是否具有哪些特定的資訊。

實際應用中，為了對抗彩虹表攻擊，樸素雜湊求交法一般會在執行時通訊雙方臨時協商一個隨機的鹽值，在雜湊計算時使用對應的鹽值進行加鹽雜湊計算。加鹽樸素雜湊的隱私集合求交一般過程為：

1. 傳送者Alice持有資料X={x1, x2, ..., xm}, 接收者Bob持有資料Y={y1, y2, ..., yn}
2. Alice和Bob使用相同的雜湊函式H
3. Alice生成隨機鹽值Salt併發送給Bob
4. Bob使用salt對所有Y進行雜湊計算hyi  = H(yi, salt)
5. Alice使用Salt對所有X進行雜湊計算hxi = H(xi, salt), 併發送hxi給Bob
6. Bob計算{hx1, hx2, ..., hxm }∩{hy1, hy2, ..., hyn }的結果為Alice和Bob資料的交集

樸素雜湊求交法，是目前PSI協議中，效能最優的協議。由於協議本身不具備安全求交能力，一般只能應用在特定問題下的非敏感資料的求交場景。

3.2 姚氏混淆電路

姚氏混淆電路（Yao’s Garbled Circuits）[2]協議由1986年由圖靈獎獲得者姚期智院士提出，用來解決著名的姚氏百萬富翁問題。混淆電路使用布林電路（與，或，非等）構建電路表，保障計算的過程中，雙方的資料不被洩露。最終根據混淆電路的計算結果，以及混淆電路表，可以計算雙方資料的計算結果。

一個典型的姚氏混淆電路的計算過程分為混淆電路生成階段,電路執行階段和電路評估階段。

1. 混淆階段，Alice生成一個布林混淆電路表，使用混淆電路表為每個布林值生成金鑰。Alice對混淆電路的計算結果，使用布林電路中對應的金鑰進行加密，打亂順序後和自己持有的資料X對應的金鑰資訊傳送給Bob。
2. 執行階段，Bob根據自己持有的資料Y，通過OT協議獲取混淆電路表對應的金鑰資訊。Bob使用自己持有的資料對應的金鑰和Alice給的金鑰對Alice傳送過來的混淆電路的計算結果進行解密，其中，只有Alice和Bob持有的資料對應的混淆電路的資料，能夠被正常解密。
3. 評估階段，Bob傳送解密後的值給Alice，Alice對照混淆電路計算結果，得出最終的計算結果。

混淆電路的設計不僅可以應用在隱私集合求交的資料相等的比較場景，也可以應用於安全的資料大小比較，模糊查詢等場景。 基於混淆電路的方案相較於熱門的基於不經意傳輸的方案在效能上處於劣勢，且同樣基於半誠實的對手模型，使得此方案目前在實際應用中使用較少。

3.3 基於同態加密

2017年，Hao Chen等人，給出基於全同態加密（FHE）的隱私集合求交方法[5]。基於同態加密的隱私集合求交方法主要是對資料進行同態加密，並使用加密後的資料和原始資料構建多項式並計算多項式的值。其主要步驟為：

1. 傳送者Alice持有資料X={x0, x1, ..., xn-1}, 接收者Bob持有資料Y={y0, y1, ..., ym-1}
2. Bob生成同態加密金鑰, 並對集合中的所有資料進行全同態加密生成新的集合C = {c0, c1, ..., cm-1}
3. Alice生成隨機一組隨機數R，並使用如下公式來計算多項式的值。Alice將計算結果的資料集{d0, d1, ..., dn-1}傳送給Bob
4. Bob對資料集進行解密，收集所有解密結果為0的資料，即是資料集X與資料集Y的交集。

在互動過程中，Alice收到的是同態加密後的資料，所以Alice不知道Bob的資料集Y的資訊。Bob收到的是經過多項式計算後的同態加密資料，如果解密後的結果為0，Bob知道對應的資料存在於Alice的資料集X中，否則解密後的資料對於Bob來說是一個隨機數。

在上述過程中，Bob對資料集Y內的所有資料進行同態加密，Alice計算高階多項式，和Bob對多項式計算結果進行解密是方案中對效能負面影響較大的行為。在Chen等人的方法中，針對這些問題進行了一些列的優化處理，其中包括使用布穀鳥雜湊方法和批處理同態加密，降低協議的計算開銷和通訊開銷。使用分窗的方法來加速高階多項式計算。

基於同態加密的隱私集合求交，只對一方的資料進行同態加密和解密，使得此方案適合雙方的資料集大小差異較大的場景（n>>m）。

同態加密演算法目前是一種低效的加密演算法，全同態加密的密文長度通常非常大，使得目前基於同態加密的隱私集合求交方案在效能上不佔據優勢。
特別地，Chen的基於全同態加密的隱私集合求交方案，只對接受者一側執行同態加密，這使得演算法適合執行在求交的集合差異較大的場景。

3.4 基於公鑰加密

基於RSA的求交法[6]最早由Meadows等人於1986年提出，協議的主要思想是通訊的雙方各自生成一個大素數，對資料進行乘方運算，並比對計算的結果。2010年，Cristofaro等人提出的基於RSA盲簽名的隱私集合求交技術[7]，是目前效能最好的基於公鑰加密的隱私集合求交技術。其一般步驟為：

1. 傳送者Alice(Server)持有資料S={s1, s2, ..., sw}, 接收者Bob持有資料C={c1, c2, ..., cv}
2. Alice和Bob使用相同的雜湊函式H和H`，Bob有持有RSA的私鑰(n, e)，並將公鑰(n, d)傳送給Alice
3. 離線階段：

3.1. Alice 使用公鑰對每個S計算hsj = H(sj), Ks:j = RSA(hsj ), tj = H`(Ks:j)
3.2. Bob 生成隨機數Rc:i (Rc:i< n 且 gcd(Rc:i, n) = 1)，並使用私鑰對資料C計算 hci = H(ci), yi = hci * RSA(Rc:i)

4. 線上階段：

4.1. Bob傳送所有yi 給Alice
4.2. Alice使用私鑰計算yi' = RSA(yi)
4.3. Alice傳送所有yi'和tj給Bob
4.4. Bob計算Kc:i = (yi' / Rc:i) mod n, ti' = H'(Kc:i)。之後計算{ t1' , t2', ..., tn' }∩{t1, t2, ..., tw}, 輸出的結果為Bob和Alice資料的交集

基於RSA的求交協議，比較典型的是RSA盲簽名求交協議。RSA盲簽名求交協議是對基於RSA的求交協議（基於RSA的金鑰交換方法）的改進方法，可以在對手是惡意模型時，安全計算資料的交集，並提供了更好的計算效能。演算法分為離線階段和線上階段，其中離線階段操作可以在資料預處理階段完成。實際執行求交演算法時，只對一方的資料執行一次RSA加密操作，相較於其它基於RSA的求交協議，具有更好的效能優勢。RSA盲簽名演算法的正確性基於如下公式(注意原論文中的Kc:i = yi' / Rc:i, 實際應為Kc:i = (yi' / Rc:i) mod n, 作者在後續論文中有糾正):

其原理是使用大數的離散對數沒有有效的計算方法的特點，Alice對Bob持有的偽隨機資料進行簽名，Bob去除偽隨機得到簽名過的自己的資料，再和Alice端的簽名資料做對比求交。

由於RSA計算複雜度較高，協議中RSA的計算次數會隨著資料量的增大呈線性增長，使得基於RSA的求交方法，在資料量較大時會產生效能問題。

由於RSA盲簽名演算法在執行時只對一端的資料進行RSA加密，使得在求交資料量級差距較大時，可以把資料量較小的一端作為Client端，這樣可以獲得非常大的效能優勢。另外，RSA演算法的流程適合並行處理，方便利用平行計算來提升效能。

RSA盲簽名協議能夠在惡意對手模型下，為隱私集合求交提供安全保障，但由於非對稱加密的次數隨比對的數量量的增加呈線性增長，所以無法處理海量資料的隱私集合求交場景。

3.5 基於不經意傳輸

OT（Oblivious Transfer）是基礎的密碼學原語，中文譯為不經意傳輸，茫然傳輸。OT協議最早於1981年由 Michael O. Rabin提出，協議由傳送方和接收方兩方參與，接收方請求獲取資訊，傳送方傳送資訊給接收方。在這個過程中，傳送方對接收方的請求資訊一無所知，同時接收方也無法獲取請求的資訊之外的額外資訊。OT協議主要利用有限的非對稱加密技術，達到安全傳輸大量資料的功能

2014年，Pinkas等人提出了基於OT擴充套件協議的高效隱私集合求交方案[8]，該方案使用OT擴充套件，傳輸資料使得通訊雙發獲得一個偽隨機函式，並使用此偽隨機函式對雙方持有的資料進行加密比對。方案主要分為三個階段來執行，雜湊階段，隱祕傳輸階段和求交階段。在雜湊階段，通訊Alice和Bob把各自持有的資料通過雜湊運算均勻分佈在一個給定大小的地址空間內，並使用隨機數填充空餘的雜湊位置。在隱祕傳輸階段，Bob根據自己持有資料的位元資訊作為選擇位，使用OT擴充套件安全地獲取Alice持有同樣位元位置上的偽隨機生成資料。最後在求交階段，Bob解密偽隨機資料，並和自己持有的而資料進行比較。

2016年，Kolesnikov使用批量OT擴充套件傳輸和布穀鳥雜湊實現了更高效的隱私集合求交方案[9]，基於OT的隱私集合求交成為效能上最僅僅樸素雜湊求交技術的隱私集合求交方案。2019年，Pinkas等人提出了基於稀疏擴充套件的隱私集合求交方案[10]，方案首先把祕密資訊分成三份，這樣在未獲取到要求交的資料之前，可以提前隨機生成兩份祕密資訊，以便在離線階段進行OT擴充套件傳輸，提前獲取偽隨機生成函式。在線上階段，為了避免傳輸大量的祕密資訊，方案使用了多項式技術，把要傳輸的資料融入多項式，僅傳遞多項式的引數來代替傳輸大量資料。根據該方案的測試結果，在要對比的資料量龐大，或者頻寬受限制場景下，此方案相較於目前最優的基於OT的隱私集合求交方案，提供了更好的效能優勢。

雖然基於不經意傳輸的隱私集合求交技術仍然是使用非對稱加密技術作為其實現原理，但不經意傳輸使用有限次非對稱加密，來完成任意數量的安全資料傳輸。基於不經意傳輸的隱私集合求交方案，是目前研究最為活躍的隱私集合求交方案。

4 隱私集合求交前景展望

隱私集合求交作為安全多方計算的關鍵技術，自誕生以來，得到了企業，個人和機構的高度的關注, 目前仍在快速發展中。近些年來，頻繁出臺的隱私和資訊保護的法律法規，促使了我國在隱私計算領域相關的研究和落地的高速發展。目前最為流行的隱私集合求交方案是基於不經意傳輸的隱私集合求交方案，對該方案的研究是基於安全性和效能平衡後的一種考量，研究的思路主要在減少非對稱加密次數和通訊雙方傳輸的資料量。

雖然隱私集合求交技術在最近這些年得到了長足的發展，但仍面臨了諸多挑戰，其中包含最流行的基於不經意傳輸協議的隱私集合求交方案是限定對手模型是半誠實模型的前提下的安全求交協議。隱私集合求交技術作為基礎應用技術，其效能仍有提升需求。目前的各種技術方案，缺少標準的對抗手段來證明其確實在實際應用中保護了資料安全。以及缺少基於隱私集合求交的各種標杆性應用。

隱私計算在金融，政務，運營商，營銷商，科研機構等對自身資料極為敏感，且對IT智慧化有強烈需求的行業和領域，有著重要的地位。對於隱私集合求交技術在實際行業應用上的實踐，需要關注的主要為題有：

1. 安全性。隱私計算為提升系統安全性而生，作為隱私計算底層關鍵性技術之一的隱私集合求交，需要在安全性方面提供令業界信服的能力和證明方式。這決定了隱私集合求交的核心技術，需要提供可信服的論文和理論依據，且通常為大眾認可的開原始碼。
2. 權威認證。隱私計算對安全性要求極為敏感，除了在演算法方面有可信理論依據之外，還需要對應的權威機構認證。這包括安全性認證的權威機構，模擬破壞性攻擊防禦能力的權威機構等。
3. 主動防禦能力。在基於智慧分析或滿足客戶設定的閾值的前提下，如果在計算過程中，應用及時識別出通訊的參與方可能包含惡意攻擊，應能夠及時停止計算並記錄判定攻擊的相關資料。
4. 可解釋性。可解釋性是更好的主動觀測計算過程和維護的能力。包含計算過程的視覺化，通訊資料抓取，事件審計能力等方案。
5. 優異的效能。作為安全通訊的底層技術，隱私集合求交需要提供相對優異的效能，以便應對海量資料處理以及實時資料分析的需求。這要求隱私集合求交演算法的效能，應儘可能去逼近樸素雜湊求交演算法的效能。

隱私集合求交目前在國內已經有商業化應用落地，但仍缺少標誌性的成功商業應用作為標杆，使得隱私計算的商業化程序在需求和質疑中緩步前行。在當前的市場背景下，如何保障今後的技術創新和應用能夠在符合法律法規的前提下，安全高效地進行資料互動，將會是未來資料密集型系統的一個重要的支撐能力。對於持有大量敏感資料的傳統企業來說，也急需一種可靠的技術，既能夠利用資料創造價值，又能夠保障持有者的資料的隱私安全。

參考文獻

[1] M. Raab and A. Steger. “Balls into bins” - a simple and tight analysis. In Randomization and Approximation Techniques in Computer Science (RANDOM’98), volume 1518 of LNCS, pages 159–170. Springer, 1998.

[2] A. C. Yao. How to generate and exchange secrets. In Foundations of Computer Science (FOCS’86), pages 162–167. IEEE, 1986.

[3] M. Bellare, V. Hoang, and P. Rogaway. Foundations of garbled circuits. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS’12, pages 784–796, 2012.

[5] Chen H, Laine K, Rindal P. Fast private set intersection from homomorphic encryption[C] //Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 1243-1255.

[6] Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//1986 IEEE Symposium on Security and Privacy. IEEE, 1986: 134-134.

[7] E. De Cristofaro, G. Tsudik, Practical private set intersection protocols with linear complexity, in: International Conference on Financial Cryptography and Data Security, Springer, 2010: pp. 143–159.

[8] B. Pinkas, T. Schneider, and M. Zohner. Faster private set intersection based on OT extension. In USENIX Security Sympo sium, pages 797–812. USENIX, 2014.

[9] V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu. Efficient batched oblivious
PRF with applications to private set intersection. In ACM CCS 2016, pages 818–829,
Vienna, Austria, October 24–28, 2016. ACM Press. 7

[10] B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai. SpOT-light: Lightweight private set
intersection from sparse OT extension. In CRYPTO 2019, Part III, LNCS 11694,
pages 401–431, Santa Barbara, CA, USA, August 18–22, 2019. Springer, Heidelberg,
Germany. 7

[11] 申立豔,陳小軍,時金橋,胡蘭蘭.隱私保護集合交集計算技術研究綜述[J].計算機研究與發展,2017,54(10):2153-2169.

[12] 黃翠婷,張帆,孫小超,等. 隱私集合求交技術的理論與金融實踐綜述[J]. 資訊通訊技術與政策,2021(6):50-56. DOI:10.12267/j.issn.2096-5931.2021.06.006.

內容來源：京東雲開發者社群https://www.jdcloud.com/