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

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

0 引言

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

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

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

1 預備知識

1.1 混淆布隆過濾器

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

1.2 安全模型

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

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

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

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

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

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

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

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

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

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

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

敵手A 贏得IND-CPA 游戲的優(yōu)勢定義為：

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

2 多方隱私集合交集協(xié)議ΠPSI

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

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

2.1 系統(tǒng)模型

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

圖2 系統(tǒng)模型Fig.2 System model

2.2 設計思路

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

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

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

2.3 協(xié)議ΠPSI描述

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

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

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

3 正確性分析

4 安全性證明

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

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

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

2）詢問。協(xié)議Π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 協(xié)議，返回執(zhí)行過OT 協(xié)議的

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

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

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

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

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

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

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

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

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

5 性能實驗與結果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結語

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