安全多方計算(5):隱私集合求交方案彙總分析

語言: CN / TW / HK

閲讀: 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 請求者數據映射流程圖

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

圖3.8 矩陣B生成示意圖

  1. 數據擁有者獲得矩陣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 不經意傳輸執行示意圖

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

圖3.10 數據擁有者數據映射流程圖

  1.  數據擁有者將其本方所有數據映射值發給請求者,請求者對比兩方數據映射值確定交集數據,而其不會獲得數據擁有者的任何非交集數據信息。至此,協議完成,

四、總結

本文介紹了基於兩方對稱數據集的三種隱私集合求交方案,其中基於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.

版權聲明

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