基于云服務(wù)器的公平多方隱私集合交集協(xié)議

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

（河南理工大學(xué) 軟件學(xué)院，河南 焦作 454000）

0 引言

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

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

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

1 預(yù)備知識

1.1 混淆布隆過濾器

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

1.2 安全模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 系統(tǒng)模型

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

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

2.2 設(shè)計(jì)思路

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

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

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

2.3 協(xié)議ΠPSI描述

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

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

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

3 正確性分析

4 安全性證明

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

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

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

2）詢問。協(xié)議ΠPSI中涉及到的預(yù)言機(jī)詢問如下：

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

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

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

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

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

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

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

①Game0：在隨機(jī)預(yù)言機(jī)模型中，Game0與真實(shí)的攻擊相對應(yīng)，由定義1 可得：

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

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

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

5 性能實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

圖3 總集合大小與存儲(chǔ)時(shí)間的關(guān)系Fig.3 Relationship between total set size and storage time

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)語

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