安全多方計算（5）：隱私集合求交方案彙總分析

閱讀： 2

一、引言

隨著數字經濟時代的到來，資料已成為一種基礎性資源。然而，資料的洩露、濫用或非法傳播均會導致嚴重的安全問題。因此，對資料進行隱私保護是現實需要，也是法律要求。隱私集合求交（Private Set Intersection, PSI）作為解決資料隱私保護的方案之一，受到廣泛關注和研究。

隱私集合求交使得持有資料參與方通過計算得到集合的交集資料，而不洩露任何交集以外的資料資訊，其功能如圖1所示。作為安全多方計算中的一個重要分支，其不僅具有重要的理論意義，也具有廣泛的應用場景。例如：隱私保護位置共享[1]、線上廣告的有效轉換率衡量以及基於人類基因組序列[2]的親子鑑定、疾病預測和血統測試等。

圖1 隱私集合求交功能示意圖

二、PSI分類

隱私集合求交的研究主要聚焦在兩個參與方，因此，本文主要針對兩方隱私集合求交進行闡述。兩方PSI可根據參與方的資料集大小分為三類，如圖2所示。根據雙方資料集大小差異可將其分為對稱資料集和非對稱資料集，對於對稱資料集，又可分為大資料集和小資料集。本文針對對稱資料集及不同場景的需求，介紹與之對應的隱私集合求交方案。

圖2 隱私集合求交分類示意圖

三、PSI方案介紹

3.1 基於DH的PSI方案

基於DH的PSI方案[3]流程如圖3.1所示，該方案基於DH金鑰交換的思路，實現兩次可以交換加密順序的加密操作，使得參與雙方對於交集資料，得到完全相同的不可逆密文。

圖3.1 基於DH的PSI方案流程示意圖

基於DH的PSI方案主要分為以下3個步驟：

1. Alice選擇隨機數作為私鑰。對於每一個數據x，Alice首先對其進行雜湊操作，再基於其雜湊值使用私鑰對其加密,生成密文，並將此密文傳送給Bob。
2. Bob選擇隨機數作為私鑰。對於每一個數據y，Bob首先對其進行雜湊操作，再基於其雜湊值使用私鑰對其加密，並將此密文傳送給Alice。對於接收到Alice的密文，Bob使用私鑰對其進行二次加密。
3. Alice對於接收到的密文，基於私鑰對其進行二次加密

結論：若Alice和Bob擁有相同的資料，則兩次加密得到的密文一致。

基於DH的PSI方案思想簡單，易於實現，但也具有一定的侷限性，例如：基於公鑰加密實現PSI功能會產生較大的計算開銷。因此，適用於資料量較小的場景。

3.2 基於OT的PSI方案

• 預備知識

不經意傳輸（Oblivious Transfer, OT）[4]是安全多方計算最基礎的協議之一，在之前的文章中已做了詳細介紹 安全多方計算(1)：不經意傳輸協議 。

本部分我們僅使用了2選1的不經意傳輸協議，其功能如圖3.2所示。Alice有兩條訊息，Bob可以通過位元b獲取訊息，而無法獲得的任何訊息。Alice無法獲得關於b的任何資訊，即：Alice不知道Bob獲取了哪條訊息。

圖3.2 不經意傳輸功能示意圖

• 方案詳解

在本部分，我們簡述經典的基於OT的PSI方案，其流程如圖3.3所示。該方案的核心思想為執行多次二選一的不經意傳輸協議，並結合偽隨機函式，使得參與雙方對於交集資料得到相同的隨機數。

圖3.3 基於OT的PSI方案流程示意圖

基於OT的PSI方案主要分為以下3個步驟：

1. Alice生成隨機數w；Bob生成隨機數，並基於與本方資料的偽隨機函式值生成.
2. Alice與Bob基於w和執行次二選一的不經意傳輸，其中為的長度。
3. Alice基於多次不經意傳輸結果生成q，Bob計算的雜湊值。
4. Alice計算本方資料的隨機值

結論：若Alice和Bob擁有相同的資料，則兩份資料得到相同的隨機值

我們以兩種極端情況論述方案的正確性：

圖3.4 基於OT的PSI方案正確性驗證

基於OT的PSI方案規避了大量的公鑰加密，使用效率更高的對稱加密完成大部分操作，但通訊開銷較大，適用於資料量較大的場景。

經典的基於OT的PSI方案仍具有很大的計算開銷及通訊開銷，但是OT的擴充套件協議為構建高效的PSI方案提供了理論支撐。在3.3中，我們以OPRF為例，介紹基於OT擴充套件協議的高效PSI方案。

3.3 基於OPRF的PSI方案

• 預備知識

不經意偽隨機函式（Oblivious Pseudorandom Function, OPRF）[5]屬於不經意傳輸的擴充套件協議，它允許執行少量的基礎OT，通過輕量級的對稱加密來實現大量的OT例項。OPRF的功能如圖3.4所示。

Alice生成偽隨機函式的金鑰k，可基於k獲得本方資料x的偽隨機函式值。Bob以本方資料y作為OPRF協議的輸入，協議執行完成後，Bob可得到y的偽隨機函式值，但無法獲得關於k的任何資訊。

圖3.5 不經意偽隨機函式功能示意圖

• 方案詳解

在本部分，我們簡述基於OPRF的PSI方案[6]，其總體流程如圖3.5所示。為便於闡述，我們將Alice作為資料擁有者，記為DO（Data Owner）；Bob作為請求者，記為Re(Requester)。

圖3.6 基於OPRF的PSI方案總體流程示意圖

我們將基於OPRF的PSI方案分為以下步驟進行闡述：

1. 請求者將資料對映為，對映過程如圖6所示。首先，請求者隨機生成m行w列的二進位制矩陣A，其中m為資料集大小。對於每個資料，請求者計算其偽隨機函式值,並將偽隨機函式值與二進位制矩陣A相結合，獲取二進位制位元串。同時，將對應位置標記為資料位（如圖3.6中藍色部分）。然後，基於二進位制位元串執行雜湊操作，得到資料對映值。

圖3.7 請求者資料對映流程圖

2. 請求者生成矩陣B。請求者生成一個m行w列的全1矩陣D，將第1步標記的資料位部分置為0。然後，將矩陣A與矩陣D執行異或操作得到矩陣B。因此，矩陣A、B具有如下特性：矩陣A、B對於資料位的位元值相同；對於非資料位的位元值相反。這一步主要是為了二選一的不經意傳輸做準備。

圖3.8 矩陣B生成示意圖

3. 資料擁有者獲得矩陣C，這一步的核心思想是請求者與資料擁有者執行w次不經意傳輸，其執行過程如圖3.8所示。通過1、2步，請求者已獲得A、B矩陣；在第3步，資料擁有者生成長度為w的二進位制位元串。在每一次OT執行中，請求者以A、B矩陣的第i列作為輸入；資料擁有者以位元串s的第i位{s[i]}作為輸入。若s[i]=0，則資料擁有者得到列；若s[i]=1，則資料擁有者得到列. 最終，資料擁有者得到矩陣C。矩陣A、B、C具有如下特性：此三個矩陣對於資料為的位元值相同；而通過不經意傳輸，矩陣C的非資料位已被置亂。

圖3.9 不經意傳輸執行示意圖

4. 資料擁有者將資料對映為,對映過程如圖3.9所示。對於每個資料，這一步與第1步的流程類似，其目的是為了對於參與雙方的交集資料生成完全相同的隨機對映值。首先，資料擁有者計算其本方資料的偽隨機函式值，並將偽隨機函式值與第3步得到的二進位制矩陣C相結合，獲取二進位制位元串然後，基於二進位制位元串執行雜湊操作，得到資料對映值。

圖3.10 資料擁有者資料對映流程圖

5.  資料擁有者將其本方所有資料對映值發給請求者，請求者對比兩方資料對映值確定交集資料，而其不會獲得資料擁有者的任何非交集資料資訊。至此，協議完成，

四、總結

本文介紹了基於兩方對稱資料集的三種隱私集合求交方案，其中基於DH的PSI方案適用於小資料的場景；基於OT的PSI方案適用於大資料集的場景，但其依然有較大的通訊開銷，因此，介紹了基於OPRF的PSI方案，其在計算開銷和通訊開銷方面均具有良好的表現。

隨著隱私計算技術的發展，多方及外包隱私集合求交方案也在被逐漸關注與研究，我們在後續文章中進行介紹。

參考文獻

[1] NARAYANAN A, THIAGARAJAN N, LAKHANI M, et al. Location Privacy via Private Proximity Testing[C]//Proceedings of the Network and Distributed System Security Symposium, NDSS 2011, San Diego, California, USA, 6th February – 9th February 2011. 2011.

[2] SHAFIN K, PESOUT T, LORIG-ROACH R, et al. Nanopore sequencing and the Shasta toolkit

enable efficient de novo assembly of eleven human genomes[J]. Nature Biotechnology, 2020(Suppl.2).

[3] 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.

[4] RABIN M O. How to Exchange Secrets by Oblivious Transfer[J]. Technical Memo TR-81, 1981.

[5] FREEDMAN M J, ISHAI Y, PINKAS B, et al. Keyword Search and Oblivious Pseudorandom

Functions[C]//KILIAN J. Theory of Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg,2005: 303-324.

[6]CHASE M, MIAO P. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF[C]//MICCIANCIO D, RISTENPART T. Advances in Cryptology – CRYPTO 2020. Cham: Springer International Publishing, 2020: 34-63.

版權宣告

本站“技術部落格”所有內容的版權持有者為綠盟科技集團股份有限公司（“綠盟科技”）。作為分享技術資訊的平臺，綠盟科技期待與廣大使用者互動交流，並歡迎在標明出處（綠盟科技-技術部落格）及網址的情形下，全文轉發。