安全多方計算(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個步驟:
- Alice選擇隨機數作為私鑰。對於每一個數據x,Alice首先對其進行雜湊操作,再基於其雜湊值使用私鑰對其加密,生成密文,並將此密文傳送給Bob。
- Bob選擇隨機數作為私鑰。對於每一個數據y,Bob首先對其進行雜湊操作,再基於其雜湊值使用私鑰對其加密,並將此密文傳送給Alice。對於接收到Alice的密文,Bob使用私鑰對其進行二次加密。
- 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個步驟:
- Alice生成隨機數w;Bob生成隨機數,並基於與本方資料的偽隨機函式值生成.
- Alice與Bob基於w和執行次二選一的不經意傳輸,其中為的長度。
- Alice基於多次不經意傳輸結果生成q,Bob計算的雜湊值。
- 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方案分為以下步驟進行闡述:
- 請求者將資料對映為,對映過程如圖6所示。首先,請求者隨機生成m行w列的二進位制矩陣A,其中m為資料集大小。對於每個資料,請求者計算其偽隨機函式值,並將偽隨機函式值與二進位制矩陣A相結合,獲取二進位制位元串。同時,將對應位置標記為資料位(如圖3.6中藍色部分)。然後,基於二進位制位元串執行雜湊操作,得到資料對映值。
圖3.7 請求者資料對映流程圖
- 請求者生成矩陣B。請求者生成一個m行w列的全1矩陣D,將第1步標記的資料位部分置為0。然後,將矩陣A與矩陣D執行異或操作得到矩陣B。因此,矩陣A、B具有如下特性:矩陣A、B對於資料位的位元值相同;對於非資料位的位元值相反。這一步主要是為了二選一的不經意傳輸做準備。
圖3.8 矩陣B生成示意圖
- 資料擁有者獲得矩陣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 不經意傳輸執行示意圖
- 資料擁有者將資料對映為,對映過程如圖3.9所示。對於每個資料,這一步與第1步的流程類似,其目的是為了對於參與雙方的交集資料生成完全相同的隨機對映值。首先,資料擁有者計算其本方資料的偽隨機函式值,並將偽隨機函式值與第3步得到的二進位制矩陣C相結合,獲取二進位制位元串然後,基於二進位制位元串執行雜湊操作,得到資料對映值。
圖3.10 資料擁有者資料對映流程圖
- 資料擁有者將其本方所有資料對映值發給請求者,請求者對比兩方資料對映值確定交集資料,而其不會獲得資料擁有者的任何非交集資料資訊。至此,協議完成,
四、總結
本文介紹了基於兩方對稱資料集的三種隱私集合求交方案,其中基於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.
版權宣告
本站“技術部落格”所有內容的版權持有者為綠盟科技集團股份有限公司(“綠盟科技”)。作為分享技術資訊的平臺,綠盟科技期待與廣大使用者互動交流,並歡迎在標明出處(綠盟科技-技術部落格)及網址的情形下,全文轉發。
- 安全多方計算(5):隱私集合求交方案彙總分析
- 2022年網路空間安全事件簡析
- 區塊鏈密碼基礎之簽名演算法(二)
- 省省省,簽名也去重:帶有去重功能的雲資料完整性審計
- 5G安全:5G-AKA連結攻擊及對策
- 告警全量分診思路分析
- 區塊鏈密碼基礎之簽名演算法(一)
- 融合與共生:區塊鏈之智慧合約
- 淺談雲原生BAS
- 全球IPv4 AS拓撲測繪初探
- Linux提權手法實戰
- 網路空間測繪——MQTT服務篇
- TTD除錯進階之ttd-bindings
- Linux核心跟蹤:ftrace hook入門手冊(下)
- 創新方案,如何更有效地預防資料洩露?
- 洞見RSA2022 | The Rise of API Security
- 除錯services.exe程序
- 超大規模的物聯網僵屍網路:Pink
- RSA 2021創新沙盒 | Apiiro公司緣何一舉奪魁?
- 【格物實驗室】製造業常見攻擊型別介紹