基于云服務器的公平多方隱私集合交集協議

張 靜，田 賀，熊 坤，湯永利，楊 麗

（河南理工大學 軟件學院，河南 焦作 454000）

0 引言

隱私集合交集（Private Set Intersection，PSI）協議是安全多方計算重要的組成部分，它允許持有各自集合的參與方在不泄露私有信息的前提下共同計算集合的交集［1-2］。PSI 技術是許多密碼協議的基礎模塊，也被廣泛應用于數據挖掘、人工智能和數據共享的安全領域，如商業廣告精準投放［3］、共同好友推薦［4］、銀行實名認證［5］、隱私保護的用戶匹配［6］、刑事案件偵查［7］等。

近年來，云計算技術的逐步應用為不同用戶之間的聯合計算提供了便捷、高效的服務，因此許多研究者利用云服務器結合混淆布隆過濾器（Garbled Bloom Filter，GBF）、不經意傳輸（Oblivious Transfer，OT）等密碼技術解決多方隱私信息交集計算問題。Inbar 等［8］基于GBF 和秘密共享提出了一種云外包多方的PSI 協議；Kavousi 等［9］基于不經意偽隨機函數提出了云外包的多方PSI 協議——多方隱私集合交集協議（Multi-party PSI protocol，MPSI），對密鑰進行秘密共享，有效避免了集合元素索引值泄露，同時使通信和計算復雜度僅取決于參與方集合元素的數量；Ben-Efraim 等［10］使用OT、GBF相結合在惡意模型下實現了多方PSI 協議——實用多方惡意安全私有集合交集PSImple；Debnath 等［11］利用布隆過濾器（Bloom Filter，BF）、同態加密、零知識證明-數據簽名結合技術設計了一種抵抗惡意敵手的云外包PSI，實現了標準模型下的安全，且取得了較低的線性復雜度；Kano 等［12］結合BF（Bloom Filter）和云服務器提出一種新的多方PSI 計算方法——隱私集合交集求和（Private Intersection Sum，PI-Sum），一定程度上規避了BF 的錯誤概率，提高了計算的準確性；Debnath 等［13］提出一種惡意安全的不經意偽隨機函數來維護PSI 協議的公平性，并使用同態加密算法來保護數據隱私；之后Debnath 等［14］又在文獻［13］的基礎上提出了基于素數階群的PSI 協議，協議使用同態加密算法來保證數據的安全性，并使用半誠實的云服務器來實現參與者之間的公平性。然而，文獻［8］中的協議在執行過程中，參與方之間的交互會造成集合元素索引值泄露。在文獻［9-12］中，只有指定參與方得到交集的結果，這種情況對于未指定的參與方并不公平。文獻［13-14］中實現了公平的PSI 計算，但是使用同態加密來保護數據隱私導致協議計算復雜度較高。

受上述文獻的啟發，本文在云服務器輔助下基于GBF 與OT 提出了一種公平多方隱私集合交集協議，記為ΠPSI。協議首先使用GBF 存儲各參與方的集合，利用秘密共享的性質達到數據安全的目的，使數據的傳輸更安全、高效；然后，利用OT 與份額置換保護了各參與方的數據隱私，避免了參與方在交互過程中可能泄露集合元素信息的問題；最后，云服務器計算出集合交集的GBF，并將它發送給各參與方，保證各參與方運行該協議可以公平地得到結果。

1 預備知識

1.1 混淆布隆過濾器

圖1 向GBF中插入元素Fig.1 Inserting elements into GBF

1.2 安全模型

半誠實參與方完全按照協議指令執行，但在協議執行過程中會記錄下收集到的一切信息，并試圖利用這些中間信息推測出額外的隱私信息。敵手會腐敗部分參與方，并根據參與方的信息試圖推導出更多隱私信息，但是不能篡改信息。

PSI 計算協議的安全性定義需滿足協議的參與者除最后的計算結果外無法得知其他參與者的任何信息。在隨機預言機模型下使用選擇明文攻擊下的不可區分性（INDistinguishability under Chosen-Plaintext Attack，IND-CPA）游戲來證明協議的安全性［17］。游戲過程如下：

1）初始化。確定挑戰者實體集合U以及兩個相同長度的消息M0和M1。

2）接收安全參數λ，挑戰者運行密鑰生成算法生成公私鑰對公開公鑰，保存私鑰。

3）查詢。概率多項式算法時間（Probabilistic Polynomial-Time，PPT）敵手A 通過預言機詢問與U進行交互，預言機詢問對敵手A 在實際攻擊中的能力進行了模擬。協議中所涉及到的預言機詢問如下：

①Execute(U)：該詢問對敵手A 的竊聽能力進行了模擬（此時A 可以獲取信道中傳送的消息），將協議實際執行過程中實體間傳送的所有消息發送給A。

③Corrupt(U，Pi)：返回的私鑰和隱私輸入數據。該詢問模擬了敵手的腐敗能力（此時A 可以腐敗部分參與方來獲取信息）。

④Collude(S)：該詢問模擬了敵手的合謀能力（此時A 可以腐敗云服務器從而獲取服務器上存儲的所有信息），返回云服務器上存儲的所有信息。

⑤Collude(V)：該詢問同樣模擬了敵手的合謀能力（此時A 可以腐敗部分參與方和云服務器來獲取他們掌握的所有信息），V?U，返回集合V中所有參與者擁有的信息以及云服務器上存儲的所有信息。

4）挑戰。敵手A將消息M0，M1發送給挑戰者，挑戰者隨機選取，加密Mb并返回密文c。

5）測試。敵手A 根據上述預言機詢問中得到的信息輸出對于b的猜測b′，若b=b′，則A 贏得游戲（記為事件Succ）。

敵手A 贏得IND-CPA 游戲的優勢定義為：

定義1 若對于任意的PPT 敵手A，存在一個函數ε使AdvA(λ) ≤ε，則稱協議是IND-CPA 安全的，其中函數ε可忽略。

2 多方隱私集合交集協議ΠPSI

為了給患者提供更加精準的醫療服務，醫院希望通過云服務商來實現不同醫院相同患者的信息共享，但是又不希望泄露各自擁有的其他患者病例信息。該問題可以轉化為基于云服務器的多方PSI 問題。本章結合GBF 與OT 技術提出基于云服務器的多方PSI 系統模型，并對具體設計思路和協議進行詳細描述，使用的參數及含義如表1 所示。

表1 參數及其含義說明Tab.1 Description of parameters and their meanings

2.1 系統模型

假設參與計算的不同醫院分別為參與方P1，P2，…，Pd，每個參與方Pi(1 ≤i≤d) 持有的患者信息為集合Xi=。希望在不泄露除交集以外的任何隱私信息的情況下，通過云服務器S計算出各自集合的交集X1∩X2∩…∩Xd，同時各參與方希望能同時得到交集的結果，具體的系統模型如圖2 所示。

圖2 系統模型Fig.2 System model

2.2 設計思路

協議ΠPSI能夠實現多方安全交集計算，在思想上等同于直接求出集合交集的GBF，查詢此交集的GBF 存儲的是否是元素的所有子份額。同時為了實現公平性，云服務器S將交集的GBF 發送給參與方Pi，參與方Pi通過查詢GBF，進而確定元素是否屬于交集。

首先，參與方Pi(1 ≤i≤d)協商使用映射范圍為[1，m]的哈希函數：H={h1，h2，…，hk}，參照1.2 節將集合元素的k份子份額依次存儲到混淆布隆過濾器的對應位置

根據哈希函數的無碰撞性可知，對于?xiq∈Xi，?xcq∈Xc(c=(i+1)%d)，若xiq=xcq，則hj(xiq)=即通過哈希映射，參與方在互不知道對方元素的情況下，總可以將相同元素存儲在具有相同索引值的GBF 中。對于給定集合Xi(1≤i≤d)及其交集X1∩X2∩…∩Xd，設GBF2是通過ΠPSI協議求得，GBF1是直接采用交集生成，如果GBF1[id]存儲的為交集中元素的子份額，則有GBF2[id]=0，id∈[1，m]。根據GBF 的創建規則可以得知GBF1[id]和GBF2[id]中存儲的結果只包含集合中的元素信息和隨機生成的λ字符串，因為GBF1[id]和GBF2[id]使用的是相同的哈希函數H，所以?id∈[1，m]，GBF2[id]存儲的是交集中元素的子份額當且僅當GBF1[id]存儲的是同一元素的子份額。同理，GBF2[id]存儲的是隨機生成的λ字符串當且僅當GBF1[id]存儲的隨機生成的λ字符串。子份額的分布僅僅取決于元素以及哈希函數，隨機字符串是均勻分布的，GBF2[id]和GBF1[id]的分布是相同的。因此，云服務器S對收到的儲存相同元素子份額的GBF 逐位異或運算必定得到

2.3 協議ΠPSI描述

多方隱私集合交集協議ΠPSI的具體描述如下：

步驟一 協商與初始化。參與方Pi(1 ≤i≤d)分別持有擁有ni個元素的集合Xi，Pi協商確定GBF 中的哈希函數：H={h1，h2，…，hk}，映射范圍為[1，m]。Pi創建GBF 并初始化為空，將集合Xi中的元素xiq拆分為k個λ位子份額，對xiq進行k次哈希得到k個索引值hj(xiq)(1 ≤j≤k)，將子份額存儲到，進而有中。在插入完集合Xi中所有元素之后，遍歷，如果為空，則

步驟五 查詢交集中的元素。云服務器S將GBF*發送給參與方Pi。參與方Pi查詢q≤ωi)確定xiq的所有子份額是否在交集之中，進而確定xiq是否為交集中的元素。

3 正確性分析

4 安全性證明

定理1 令G是一個階為大素數p的循環群，A 是在多項式時間tA內攻擊IND-CPA 安全性的PPT 敵手。設A 可發送少于qexe次的Execute 詢問和qsen次的Send 詢問，最多qh次的隨機預言機詢問，因此有：

證明 敵手A 攻擊協議ΠPSI的IND-CPA 安全性，構建一個敵手B 通過A 來攻擊DDH 問題。如果A 能夠以不可忽略的優勢ε攻破IND-CPA 安全性，B 可以不可忽略的優勢攻破DDH 問題。過程如下：

1）初始化。確定挑戰用戶實體集合U以及兩個相同長度的消息M0和M1發送給B。用戶實體集合U包括協議ΠPSI中的d個參與者以及一個服務器S。B 根據安全參數λ生成公私鑰對(pk1，sk1)，(pk2，sk2)，保留私鑰sk1，sk2，則B 的挑戰四元組為

2）詢問。協議ΠPSI中涉及到的預言機詢問如下：

①H(M)：若列表L已存在記錄(M，r)，則返回r；否則隨機選取r∈G，將記錄(M，r)存儲進列表L，返回r。

②Send(Pi，Pc)：參與方Pi(1 ≤i≤d) 和參與方Pc(c=(i+1)%d)之間運行k-out-of-mOT 協議，返回執行過OT 協議的

③Send(Pi)：參與方Pi進行份額置換操作，返回

④Send(Pi，S)：云服務器S對收到的進行逐位異或運算得到交集的GBF*，返回GBF*。

⑤Execute(Pi，S)：基于Send 詢問成功的情況，返回

⑥Corrupt(Pi)：返回參與方Pi的數據集Xi。

進一步通過一系列的混合游戲Gamen(n∈[0，4])來證明定理1，從游戲中敵手的真實攻擊開始，到游戲中敵手的沒有任何優勢時結束。

①Game0：在隨機預言機模型中，Game0與真實的攻擊相對應，由定義1 可得：

②Game1：除了通過列表L中的記錄來模擬預言機中哈希函數，其余部分與Game0相同，仍與真實的攻擊相對應。因此Game1與現實中敵手攻擊是不可區分的，故有

③Game2：除了中止H(x)和H(y)哈希碰撞，其余部分同Game1一樣。根據生日悖論可知，發送qexe次的Execute 詢問、qsen次的Send 詢問和qh次的隨機預言機詢問時，發生哈希碰撞的概率最多為pr2，故

⑤Game4：通過DDH 來模擬協議ΠPSI的執行。給定DDH樣 例 (A=gx，B=gy)，隨機選擇α，β∈Ζp，令E(x)=Aα，E(y)=Bβ，存在四元組DDH(g，A，B，DDH(E(x)，E(y)))。事件Exp4發生當敵手A對預言機的哈希H′進行了E(x)=Aα，E(y)=Bβ詢問，且存在：

5 性能實驗與結果分析

本章對ΠPSI協議的計算復雜度與通信復雜度以及協議的運行時間進行了分析，與相關的PSI 協議的性能對比結果如表2 所示。

表2 不同方案的PSI性能分析Tab.2 PSI performance analysis of different schemes

ΠPSI協議中d個參與方兩兩之間運行k-out-of-mOT 協議和份額置換時共需要dλm個字符操作。d個參與方向云服務器S發送GBF 時需要dλm個字符操作。因此，協議的計算復雜度為O(dλm)，通信復雜度為O(dλm)。可以看出，ΠPSI協議的計算復雜度和通信復雜度都與參與方集合所包含的元素總個數ω無關。這是由于ΠPSI協議將集合中的元素存儲進大小為m的GBF 之中，之后所有的操作都是基于GBF 來對數據進行處理的。因此，與文獻方案相比，ΠPSI協議具有較優的計算性能。此外，ΠPSI協議還具有公平性，即所有參與方同時獲取PSI 的計算結果。

為了更直觀地對比本文協議與MPSI［9］、PSImple［10］和PISum［12］的時間開銷，本文進行了仿真實驗和結果分析。需要指出的是，協議所耗費的時間指10 次實驗中的平均耗時。實驗配置：搭載Intel Core i5-5200U CPU @ 2.20 GHz，機帶RAM 4.00 GB，x64 處理器的筆記本電腦。

考慮集合包含元素總個數的變化對協議存儲時間的影響。假設參與方數量d=20；哈希函數個數k=128；安全參數λ=128；混淆布隆過濾器大小m=105。分別選取集合包含的元素個數ω=28，29，210，211，212進行對比實驗，總集合大小和協議存儲時間的關系如圖3 所示。

圖3 總集合大小與存儲時間的關系Fig.3 Relationship between total set size and storage time

根據圖3 可以看出，隨著總集合大小的增加，所有方案的存儲時間基本呈線性增加，但當固定總集合大小時，本文的ΠPSI協議具有最低的存儲時間。

考慮集合包含元素總個數的變化對協議通信開銷的影響。假設參與方數量d=20；哈希函數個數k=128；安全參數λ=128；混淆布隆過濾器大小m=105。分別選取集合包含的元素個數ω=28，29，210，211，212進行對比實驗，總集合大小和協議通信開銷的關系如圖4 所示。

圖4 總集合大小與通信開銷的關系Fig.4 Relationship between total set size and communication overhead

根據圖4 可以看出，隨著總集合大小的增加，所有方案的存儲時間基本呈線性增加，但當固定總集合大小時，本文的ΠPSI協議具有最低的通信開銷。

考慮集合包含的元素總個數變化對運行時間之間的影響。假設參與方數量d=20；哈希函數個數k=128；安全參數λ=128；混淆布隆過濾器大小m=105。分別選取集合包含的元素個數ω=28，29，210，211，212進行對比實驗，協議運行時間與集合包含元素個數的關系如圖5 所示。

圖5 總集合大小與協議運行時間的關系Fig.5 Relationship between total set size and running time

根據圖5 可以看出，隨著總集合大小的增加，所有方案的運行時間基本呈線性增加。但ΠPSI協議的運行時間增長速率最慢。且當固定總集合大小時，本文的ΠPSI協議具有最低的運行時間。

此外，ΠPSI協議中參與方個數的變化對協議的運行時間也會產生一定的影響。假設集合包含的元素總個數ω=103，保持其余參數不變。分別選取參與方個數d=101，102，103，104，105進行對比實驗，協議運行時間與參與方個數的關系如圖6 所示。

圖6 參與方個數與協議運行時間的關系Fig.6 Relationship between number of parties and running time

由圖6 可以看出，所有協議的運行時間都隨參與方個數的增多而逐漸增加。但當參與方個數固定時，協議ΠPSI的時間開銷均低于其他方案。

綜上，ΠPSI協議在一定程度上節約了多方PSI 的存儲開銷、通信開銷和計算的時間開銷，提高了計算效率，此外根據協議ΠPSI的執行過程可知，參與方Pi(1 ≤i≤d)在協議的步驟五中可以同時得到交集所對應的混淆布隆過濾器GBF*，通過本地查詢可以得到交集的結果，實現了公平多方PSI 計算。因此，協議ΠPSI的整體效率優于所對比的文獻。

6 結語

隱私集合交集計算是安全多方計算的特定問題，常被用于智慧醫療、商業廣告等領域，但現有多方PSI 協議中參與方存在不公平性問題，因此提出了一個基于云服務器外包的公平多方PSI 協議。利用GBF 和OT 的結合，將交集的計算轉換為GBF 的逐位異或運算。協議執行結束后，參與方均能得到交集結果，實現了公平性。理論分析和實驗結果表明本文所提出的協議在實現公平性的同時又有著較低的存儲、通信和計算時間開銷。隨著區塊鏈技術的不斷發展，存在著數據的安全共享與數據的高速流通問題，因此，下一步要研究將區塊鏈技術與云服務器結合構建公平多方PSI 協議。