高效且惡意安全的三方小集合隱私交集計算協(xié)議

張 蕾 賀崇德 魏立斐

1(上海海洋大學(xué)信息學(xué)院 上海 201306) 2(上海海事大學(xué)信息工程學(xué)院 上海 201306)

隱私集合交集(private set intersection, PSI)技術(shù)是安全多方計算技術(shù)的重要應(yīng)用之一.經(jīng)典的PSI協(xié)議允許2個參與方各自持有自己的私有集合，在協(xié)議結(jié)束時兩方或其中一方作為接收者，獲得兩方集合的交集，且不會泄露除交集之外的任何元素信息[1-2].作為重要的密碼學(xué)工具，PSI也被廣泛應(yīng)用于人工智能和數(shù)據(jù)挖掘的安全領(lǐng)域，如隱私保護數(shù)據(jù)挖掘[3-4]、私有通訊錄查找[5]、新冠接觸者追蹤[6]以及衡量在線廣告轉(zhuǎn)化率[7]等.在數(shù)據(jù)共享的時代背景下，多方參與PSI的場景需求更加廣泛，例如在社交軟件的隱私聯(lián)系人查找功能中，可查找多個用戶的共同好友即屬于多方參與PSI的應(yīng)用場景.

目前大多數(shù)高效的PSI方案都是基于不經(jīng)意傳輸(oblivious transfer, OT)協(xié)議[8]構(gòu)建，得益于高效的OT擴展技術(shù)，各方可以通過少量的公鑰操作生成大量的OT協(xié)議實例，使得基于OT的PSI協(xié)議所需要的公鑰操作數(shù)量僅與安全參數(shù)有關(guān)，而與集合大小無關(guān)，計算成本較低，從而高效地構(gòu)造PSI協(xié)議[9-15]，但其通常具有一定的固定成本，往往僅適合大集合(210～220個元素)場景，而在小集合(500個元素或者更少)場景下優(yōu)勢不夠明顯.此外，雖然基于OT的協(xié)議計算效率較高，但同時帶來了巨大的通信成本，而在某些實際場景下通信成本比計算成本更重要[16].

基于密鑰協(xié)商構(gòu)造的PSI協(xié)議[17-20]一般通信量較低，在弱通信場景中具有較大優(yōu)勢.例如，采用目前最有效的1-out-of-2 OT[21]構(gòu)建PSI，128個基本OT需要花費384個群元素進行通信以及640次指數(shù)運算，其開銷比集合大小為200的基于Diffie-Hellman密鑰協(xié)商的PSI還要昂貴[16].從實用成本的角度，在網(wǎng)絡(luò)中添加CPU比擴大網(wǎng)絡(luò)容量要便宜的多，因此，在谷歌內(nèi)部部署PSI功能時選擇了基于Diffie-Hellman密鑰協(xié)商的PSI[16].此外，基于RSA和全同態(tài)加密的協(xié)議也具有很低的通信成本[22-26]，常被用于弱通信場景中，但其采用大量繁重的公鑰操作，產(chǎn)生了巨大的計算成本，導(dǎo)致非常低的運算效率.

小集合交集計算是PSI協(xié)議的一個典型場景，具有廣泛的應(yīng)用.例如，為了增強了蘋果手機的隔空投送功能，文獻[27]通過對用戶的整個地址薄(幾千項)和另一個用戶的個人標(biāo)識符(電活號碼或電子郵箱，可能是10項)進行PSI.又如，各方可能希望利用可用日歷時間的PSI來安排在線會議時間，即各自可用時間集合(按小時劃分，此時集合規(guī)模約為360小時[20])的交集.對于此類輸入大小的集合，基于密鑰協(xié)商的PSI是計算成本最低的.Rosulek等人[20]在CCS 2021上采用Diffie-Hellman密鑰協(xié)商和多項式插值技術(shù)，在小集合情況下實現(xiàn)了迄今為止最快的PSI方案.然而，文獻[20，27]所述的基于密鑰協(xié)商的方案都僅適用于具有2個參與方的場景.PSI協(xié)議的隱私性要求除交集之外的任何信息都無法被泄露，而兩方協(xié)議直接擴展到多方將不可避免地泄露交集之外的兩兩相交的部分，導(dǎo)致兩方協(xié)議無法直接擴展到多方.

綜上，本文提出了一個基于密鑰協(xié)商的三方惡意安全PSI協(xié)議，能抵抗任意2個惡意參與方合謀，實現(xiàn)了現(xiàn)有多方PSI中最低的通信量；特別地，在小集合場景下，保持了較高的運算效率.該協(xié)議非常適合三方小集合場景，例如為了簽訂合同，投資方、勞務(wù)方和中介方希望利用1個月內(nèi)的可用時間安排會議，需要3個參與方利用各自可用時間的集合，考慮存在合謀的情況下，不泄露各方集合信息時求出交集.本文的主要貢獻有2個方面：

1)提出了一個基于密鑰協(xié)商的三方PSI協(xié)議，實現(xiàn)了半誠實的安全性，允許任意2個參與方合謀，并在此基礎(chǔ)上提出了惡意安全的三方PSI協(xié)議.利用模擬范式，證明了協(xié)議在半誠實和惡意安全模型下合謀時的安全性.

2)通過實驗仿真，在大集合場景，相比現(xiàn)有基于OT的多方PSI協(xié)議，本文協(xié)議具有最優(yōu)的通信輪數(shù)，通信量降低了89%～98%；在小集合場景，相比適用弱通信網(wǎng)絡(luò)的同類PSI協(xié)議，具有最優(yōu)的運行時間和通信負(fù)載，其中運算速度比依賴于同態(tài)加密的PSI協(xié)議快10～25倍.

1 相關(guān)工作

PSI作為安全多方計算的熱點問題已經(jīng)得到了快速的發(fā)展.經(jīng)典的PSI協(xié)議包含2個參與方，已經(jīng)達(dá)到非常高的效率.最早的PSI協(xié)議采用樸素哈希的方式，即先對集合元素求哈希，并通過對哈希值的對比得出交集，這種方案是十分高效的，但容易受到碰撞攻擊.為了解決碰撞攻擊的問題，需要采用安全對比的方法.對于持有m個元素的集合的雙方，為了求出交集元素，最壞的情況需要進行O(m2)次比較.通過將元素映射到長為n的布隆過濾器，比較次數(shù)可減少到O(nlbn).隨著PSI技術(shù)的成熟，通過布谷鳥哈希、不經(jīng)意偽隨機函數(shù)和高效的OT擴展等技術(shù)，一些PSI協(xié)議實現(xiàn)了O(n)的計算和通信復(fù)雜度.

最新對抗半誠實敵手的兩方PSI協(xié)議來自文獻[9].文獻[9]設(shè)計了一種基于OT技術(shù)的安全字符串相等性測試協(xié)議，僅使用OT[8]、哈希函數(shù)、對稱密鑰加密操作和按位操作來構(gòu)建協(xié)議，因此計算效率很高.文獻[10]基于OT擴展和多項式編碼技術(shù)實現(xiàn)，除基于昂貴的RSA和FHE的協(xié)議之外，該協(xié)議在已有的兩方PSI中具有最低的通信.文獻[11]提出了一種高效的多點不經(jīng)意偽隨機函數(shù)(oblivious pseudo-random function, OPRF)，實現(xiàn)了計算和通信之間更好的平衡，在具有中等帶寬的網(wǎng)絡(luò)中達(dá)到了所有已知協(xié)議中最高的運行效率.最新惡意安全兩方PSI協(xié)議是文獻[28]和文獻[29]，它們分別基于高效的OT擴展和向量OLE[30].當(dāng)集合比較大(例如n>220)時，文獻[29]非常高效，但它具有較高的固定成本，這使得它在較小的集合場景中效率較低.

隨著隱私集合交集技術(shù)的成熟及其在實際應(yīng)用中的普及，2個參與方已經(jīng)不能滿足應(yīng)用需求，多參與方的場景更加廣泛，但目前僅有少數(shù)方案適用于此類場景.第1個高效的多方PSI協(xié)議由Kolesnikov等人[31]提出，該協(xié)議同樣使用OT擴展實現(xiàn)，他們?yōu)閰f(xié)議設(shè)計了2個版本，分別實現(xiàn)了半誠實及增強半誠實(可能在執(zhí)行開始前改變攻陷參與方的輸入)的安全性.Efraim等人[32]巧妙地結(jié)合了來自半誠實安全的多方PSI[33]和惡意兩方PSI[34]的結(jié)果，提出了第1個惡意安全的多方PSI，但該協(xié)議需要傳輸混亂布隆過濾器(garbled Bloom filter, GBF)進行通信，這帶來了巨大的通信負(fù)擔(dān).Nevo等人[35]首先使用高效的不經(jīng)意鍵值存儲(oblivious key-value stores, OKVS)技術(shù)[36]和高效不可信云輔助兩方PSI實現(xiàn)了迄今為止最快的惡意多方PSI協(xié)議，但該協(xié)議在惡意參與者合謀的情況下是不安全的，會泄露其他方的集合元素信息.利用不經(jīng)意零共享技術(shù)和不經(jīng)意可編程偽隨機函數(shù)(oblivious programmable pseudorandom function, OPPRF)，Nevo等人[35]在第2個協(xié)議中實現(xiàn)了允許任意t個參與方進行合謀的惡意PSI協(xié)議，實現(xiàn)了已有惡意協(xié)議中最好的計算和通信效率.

基于密鑰協(xié)商構(gòu)建PSI協(xié)議是隱私集合交集計算的經(jīng)典思路，也是本文工作的重點.最早的基于密鑰協(xié)商的PSI協(xié)議可以追溯到1999年提出的文獻[17]，并實現(xiàn)了半誠實的安全性，但由于該協(xié)議完全按照Diffie-Hellman協(xié)議設(shè)計，導(dǎo)致其在半誠實安全下變體的設(shè)計空間非常有限.之后的研究中，基于Diffie-Hellman的PSI協(xié)議在惡意敵手存在情況下的安全性得到增強.文獻[18-19]提出了高效且惡意安全的PSI方案，實現(xiàn)了線性的通信復(fù)雜度和線性的計算復(fù)雜度.最新的文獻[20]利用多項式插值將參與方集合元素映射到Diffie-Hellman密鑰協(xié)商的密鑰空間，通過對比輸出密鑰得出交集，分別實現(xiàn)了半誠實和惡意安全性，并極大地提高了基于密鑰協(xié)商的PSI的效率，尤其是在小集合的情況下，該方案提出的惡意安全協(xié)議甚至比同類半誠實安全協(xié)議的運算速度快，同時通信成本降低了40%.但上述基于密鑰協(xié)商的PSI協(xié)議都僅適用于兩方，且無法直接擴展到多個參與方的場景.

2 預(yù)備知識

2.1 安全模型

安全多方計算的安全模型可以分為半誠實模型和惡意模型2種.在半誠實模型下，敵手完全遵循協(xié)議的執(zhí)行過程，但可能會記錄協(xié)議執(zhí)行過程中的所有數(shù)據(jù)，并試圖從協(xié)議執(zhí)行過程數(shù)據(jù)中獲取額外信息；在惡意模型中敵手不僅可以通過協(xié)議過程的數(shù)據(jù)推測敏感信息，還可以不遵循協(xié)議規(guī)范，拒絕參與協(xié)議、修改隱私的輸入集合信息或者提前終止協(xié)議的執(zhí)行等.本文提出的協(xié)議分別在半誠實模型和惡意模型下可證安全而不泄露任何信息，且允許任意2個參與方的合謀.

針對安全多方計算的協(xié)議普遍采用模擬范例進行證明，將理想狀態(tài)下引入可信第三方的安全多方計算協(xié)議的理想?yún)f(xié)議與真實協(xié)議進行對比，如真實協(xié)議的視圖與理想?yún)f(xié)議的視圖是不可區(qū)分，則真實協(xié)議未泄露更多信息，進而證明協(xié)議是安全的.在半誠實模型中，模擬器僅需根據(jù)協(xié)議規(guī)則模擬敵手視圖，并證明與真實協(xié)議的視圖是不可區(qū)分.在惡意模型中，需要進一步考慮敵手的惡意行為，對惡意參與方進行輸入提取，并考慮其對誠實參與方輸出的影響嚴(yán)格進行模擬，最終證明模擬器與真實協(xié)議的視圖不可區(qū)分.

本文協(xié)議包含3個參與方，可以抵抗任意兩方的合謀攻擊.在三方協(xié)議中，需要對任意兩方合謀進行模擬，證明模擬器視圖與真實協(xié)議視圖計算不可區(qū)分.

定義2.惡意模型安全性.設(shè)f是理想狀態(tài)下的三方協(xié)議，π為真實協(xié)議.如果對于現(xiàn)實模型中所有使用概率多項式時間算法的敵手A都存在一個理想模型中使用概率多項式時間算法的模擬器S，使得

即敵手A在真實協(xié)議中得到的信息與理想模型得到的信息是不可區(qū)分，則稱協(xié)議π在惡意敵手存在的情況下安全地計算了f，其中x,y,z為參與方的輸入，n為安全參數(shù).

2.2 三方PSI的理想功能

3個參與方各自擁有自己的私有集合，通過聯(lián)合執(zhí)行三方PSI協(xié)議，接收方獲得3個參與方集合交集元素的信息，除此之外各參與方無法獲取任何額外信息.另外，敵手會設(shè)置狀態(tài)abort，若abort=1，則協(xié)議會中止.特別地，在半誠實模型中，敵手總是設(shè)置abort=0.圖1描述了三方PSI的理想功能，其中[n]表示整數(shù)集合{1,2,…,n}.

2.3 理想置換

在理想置換模型中，各方可以訪問{0,1}n上的隨機置換Π及其逆置換Π-1，在安全性證明中，模擬器可以觀察理想置換Π,Π-1上所有查詢并編碼響應(yīng)，為模擬敵手的視圖提供幫助.目前，理想置換已被用于實現(xiàn)混亂電路和OT協(xié)議中哈希函數(shù)[37-38].理想置換也可以用于設(shè)計安全的PSI協(xié)議，文獻[20]利用理想置換分別實現(xiàn)了半誠實和惡意敵手的安全性.

2.4 雙線性配對

雙線性配對廣泛應(yīng)用于密碼方案的設(shè)計[39].設(shè)G是素數(shù)q階加法循環(huán)群，GT是q階乘法循環(huán)群.映射e:G×G→GT滿足下列性質(zhì)，則被稱為一個雙線性配對映射：

1)雙線性.對于任意的P,Q∈G，a,b∈*p，則有e(aP,bQ)=e(P,Q)ab.

2)非退化性.存在P,Q∈G，使得e(P,Q)≠1GT，其中1GT是GT中的單位元.

3)可計算性.對于任意的P,Q∈G，存在有效的多項式時間算法可以計算e(P,Q).

本文方案的安全性主要基于判定性雙線性(decision bilinear Diffie-Hellman, DBDH)假設(shè):對于P∈G，給定(P,aP,bP,cP)和元素h∈GT，判斷e(P,P)abc和h是計算不可區(qū)分的，即對于任意的多項式時間算法F及任意的n，均有:

Pr[F(P,aP,bP,cP,e(P,P)abc)=1]-

Pr[F(P,aP,bP,cP,h)=1]≤ε(n),

其中ε(n)是參數(shù)為n的可忽略函數(shù).

2.5 三方密鑰協(xié)商協(xié)議

本文設(shè)計的三方PSI協(xié)議是基于文獻[40]提出的三方Diffie-Hellman密鑰協(xié)商協(xié)議.文獻[40]的協(xié)議僅需要一輪通信即可構(gòu)建一個共享的密鑰.三方密鑰協(xié)商協(xié)議過程如圖2所示.該協(xié)議包含3個參與方A,B,C，給定雙線性配對e:G×G→GT，其中G是素數(shù)q階加法循環(huán)群，GT是q階乘法循環(huán)群.P是G的一個生成元，A,B,C各隨機選擇a,b,c∈*p，分別廣播aP,bP,cP.根據(jù)雙線性配對性質(zhì)，三方均可以計算共享密鑰K=e(bP,cP)a=e(aP,cP)b=e(aP,bP)c=e(P,P)abc.

3 三方隱私集合交集計算協(xié)議

本節(jié)首先介紹了第一個半誠實版本的協(xié)議1(PSI-s)，主要思想來源于三方密鑰協(xié)商[40]，僅需兩輪通信.協(xié)議要求各參與方是半誠實的，同時允許任意兩方合謀.通過改進半誠實版本的協(xié)議，在協(xié)議2(PSI-m)中達(dá)到了惡意攻擊安全.在協(xié)議描述中，用K表示密鑰協(xié)商中輸出密鑰空間，κ表示計算安全參數(shù)，λ表示統(tǒng)計安全參數(shù).

3.1 半誠實三方隱私集合交集協(xié)議(PSI-s)

3.1.1 基本協(xié)議

基于密鑰協(xié)商的三方PSI協(xié)議的主要想法是將參與方的元素與輸出密鑰用插值多項式聯(lián)系起來：若元素在集合的交集中，則輸出相同的密鑰，否則將輸出不同的密鑰，這個過程不會泄露任何信息.

協(xié)議模型結(jié)構(gòu)如圖3所示.3個參與方A,B,C，其中參與方C作為接收者，在協(xié)議執(zhí)行結(jié)束之后獲得三方集合交集的元素信息.協(xié)議將集合元素映射到密鑰協(xié)商后的公共密鑰空間上，若三方獲得的公共密鑰相同，則可判斷對應(yīng)的元素在交集中，否則該元素不在交集中.事實上，將元素映射到3個參與方的密鑰空間是不必要的，本節(jié)中提出的協(xié)議僅僅將元素映射到參與方B,C的密鑰空間，這大大降低了協(xié)議所需的計算量和通信量.

半誠實三方PSI的完整協(xié)議在協(xié)議1中給出.參與方A通過插值多項式，將所有xi∈X與用于生成共享密鑰的參數(shù)aiP進行關(guān)聯(lián)，并通過理想置換Π-1(aiP)使得生成的多項式與隨機選取的同階多項式不可區(qū)分，從而保證了集合X中元素的隱私性.參與方B和C通過對來自A的多項式求響應(yīng)，并最終求出共享密鑰，分別隱含了X∩Y和X∩Z的信息.最終C通過對比共享密鑰，即可得出三方集合交集，不會泄露除交集外的任何元素信息.

協(xié)議1.基于密鑰協(xié)商的半誠實三方PSI(PSI-s).

參數(shù)：3個參與方A,B,C；有限域F，循環(huán)群G和GT，P是G的生成元；理想置換Π,Π-1：F→F;雙線性配對e:G×G→GT；隨機密鑰空間|K|≥2λ+2 lb n.

輸入：參與方A,B,C分別輸入集合X,Y,Z；

輸出：接收方C輸出集合X∩Y∩Z.

協(xié)議過程如下：

1)B隨機選擇b∈*p計算bP發(fā)送給C，同時C

隨機選擇c∈*p計算cP發(fā)送給B.

2)A隨機選擇n個隨機值{a1,a2,…,an}∈*p，插值多項式Q(xi,Π-1(aiP))并發(fā)送給B,C.

3.1.2 正確性分析

因此，對于交集中的元素xi=yi=zi，有：

e(P,P)aibc=e(aiP,cP)b=

3.1.3 安全性證明

定理1.假設(shè)Π,Π-1是理想置換，協(xié)議1在半誠實模型下安全地實現(xiàn)了三方隱私集合交集計算，其安全性歸約于判定性雙線性問題的困難性假設(shè).

證明.在本文的協(xié)議中，任意2個參與方合謀即為最大的合謀攻擊，因此只需要證明協(xié)議對任意2個參與者合謀時是安全的，則對于任意單個半誠實參與方也是安全的.分3種情況分別討論.

1)半誠實的參與方A與B合謀情況

在參與方A,B合謀的情況下，敵手從誠實參與方C接收到的唯一消息是cP，由于c是在*p中隨機選取的，cP和G中隨機值是不可區(qū)分的.因此，在A,B合謀的情況下，A,B未獲得任何有用信息.

2)半誠實的參與方B與C合謀情況

在參與方B,C合謀的情況下，敵手獲得的消息是來自誠實參與方A的多項式Q(·)，因Π是理想置換，每一個Π-1(aiP)值與隨機值是不可區(qū)分的，因此Q(·)是一個輸出隨機均勻的多項式而與輸入x無關(guān)，Q(·)與隨機選取的同階多項式是無法區(qū)分的，B,C未獲得任何有用信息.

3)半誠實的參與方A與C合謀情況

設(shè)計以下模擬器S來證明它和真實協(xié)議是不可區(qū)分的.定義混合序列hybridh：步驟①S按照協(xié)議規(guī)則誠實地發(fā)送bP給參與方C；步驟②對于zi∈(X∩Y∩Z)∪{zi|i≥h}，模擬器計算ki=e(Π(Q(zi)),bP)c，其中Π由參與方A決定；步驟③對于所有其他的zi∈Z，選擇隨機值作為ki的輸出；步驟④S生成集合K.

此時，hybrid0即為真實協(xié)議，而hybridn即為設(shè)計的模擬器.在hybridn中只利用了交集X∩Y∩Z中的元素生成信息，所以不會泄露不在交集中元素的任何信息.

為了證明hybridh和hybridh+1是不可區(qū)分的，修改上述混合序列步驟③為：若zh?X∩Y∩Z,模擬器計算kh=k*；對于所有其他的zi∈Z，選擇隨機值作為ki的輸出.

此時，上述混合序列在k*被賦予不同的值時分別對應(yīng)于hybridh和hybridh+1.在hybridh中，k*被計算為k*=e(Π(Q(zi)),bP)c，而在hybridh+1中k*被賦予隨機值.根據(jù)參數(shù)選取的隨機性和雙線性配對的性質(zhì)易知，hybridh和hybridh+1是不可區(qū)分的，從而證明了模擬器和真實協(xié)議也是不可區(qū)分的.

綜合1)～3)知，協(xié)議1在半誠實模型下安全地實現(xiàn)了基于密鑰協(xié)商的三方隱私集合交集計算且能夠抵抗合謀攻擊.

證畢.

3.2 惡意安全三方隱私集合交集協(xié)議(PSI-m)

3.2.1 基本協(xié)議

協(xié)議2.基于密鑰協(xié)商的惡意三方PSI(PSI-m).

參數(shù)：3個參與方A，B，C；有限域F，循環(huán)群G和GT，P是G的生成元；理想置換Π,Π-1：F→F;雙線性配對e:G×G→GT；抗碰撞的哈希函數(shù)H1：{0,1}*→F,H2：{0,1}*×GT→{0,1}2κ；隨機密鑰空間|K|≥2κ.

輸入：參與方A，B，C分別輸入集合X，Y，Z；

輸出：接收方C輸出集合X∩Y∩Z.

協(xié)議過程如下：

1)B隨機選擇b∈*p計算bP發(fā)送給C，同時C

隨機選擇c∈*p計算cP發(fā)送給B.

2)A隨機選擇n個隨機值{a1,a2,…,an}∈*p，并對每一個xi∈X求哈希值H1(xi).隨后插值多項式Q(H1(xi),Π-1(aiP))發(fā)送給B,C.

3)B,C接收多項式，若多項式階數(shù)小于1，則協(xié)議終止.

4)B計算輸出密鑰.B對每一個yi∈Y求哈希值H1(yi)，然后用H1(yi)對來自參與方A的多項式Q(·)求值，并計算對應(yīng)的共享密鑰值ki=e(Π(Q(H1(yi))),cP)b.

3.2.2 正確性分析

與3.1.2節(jié)類似，對于交集中元素xi=yi=zi有：

H2(zi,ki)=H2(zi,e(Π(Q(H1(zi))),bP)c)=

H2(zi,e(aiP,bP)c)=H2(zi,e(P,P)aibc)=

H2(yi,e(aiP,cP)b)=H2(yi,

e(Π(Q(H1(yi))),cP)b)=H2(yi,ki).

因此，滿足H2(yi,ki)∈K的元素即是交集X∩Y∩Z的元素.

3.2.3 安全性證明

考慮到參與方的合謀情況，安全性證明分為3種情況，在定理2～4中分別討論.

定理2.假設(shè)Π,Π-1是理想置換，協(xié)議2在惡意參與方B,C合謀的情況下是安全的.

證明.由于誠實參與方并未收到任何來自惡意參與方B,C的輸入，所以在B,C合謀的情況下，不需要考慮敵手對誠實參與方輸出的影響，也即不需要進行輸入提取.因Π是理想置換，每一個Π-1(aiP)的輸出值都是一個均勻隨機的，因此多項式Q(·)與輸入x無關(guān)，Q(·)與隨機選取的同階多項式是無法區(qū)分的.B,C未獲得任何有用信息，從而證明了在惡意參與方B,C合謀的情況下，協(xié)議2安全地實現(xiàn)了隱私交集計算的功能.

證畢.

定理3.假設(shè)H1,H2是隨機預(yù)言機，Π,Π-1是理想置換，則協(xié)議2在惡意參與方A,C合謀的情況下安全性歸約于判定性雙線性問題的困難性假設(shè).

證明.首先刻畫模擬器S的能力：

1)S誠實地扮演隨機預(yù)言機H1,H2和理想置換Π±的角色.

① 對于所有敵手發(fā)出的查詢H1(y)，若未查詢過y，則S隨機選取元素h1作為返回，并將(y,h1)記錄在列表O1中；否則直接返回O1中的對應(yīng)值.

② 對于每一個敵手發(fā)出的查詢H2(y,k)，若未查詢過(y,k)，則S隨機選取元素h2作為返回，并將(y,k,h2)記錄在列表O2中；否則直接返回O2中的對應(yīng)值.

③ 對于每個查詢Π-1(m)，若未查詢過Π(f)，則S隨機選取元素f作為返回，并將(f,m)記錄在列表OΠ中；否則直接返回OΠ中的對應(yīng)值.

4)S最終將K發(fā)送給敵手.

以下通過混合序列hybridh，證明了這個模擬協(xié)議與真實協(xié)議是無法區(qū)分的.

1)hybrid0.這是真實的交互，與參與方B按照協(xié)議規(guī)則誠實地運行，其中K定義為

K={H2(y,e(Π(Q(H1(y))),cP)b)|y∈Y}，

同時，列表O1，O2和OΠ也被生成.

2)hybrid1.與hybrid0唯一的不同是：在計算ki時，若存在y∈Y滿足y?O1但Q(H1(y))∈OΠ，則交互終止.這意味著敵手從未查詢H1(y)，但Q(H1(y))卻是它從Π-1輸出的值.這種概率是可忽略的：對于任意f∈OΠ，多項式等式Q(·)=f至多有n個解且在F中均勻分布，因此至少有n/|F|概率滿足Q(H1(y)=f).假設(shè)敵手對H1做了共q次查詢，通過n個y∈Y和q個f∈OΠ，總概率為n2q/|F|，這是可忽略的.

3)hybrid2,i.對于每一個i∈[q]，對于形式為Π(f)=m的前i次查詢中，若從未查詢過Π-1(m)，則將f添加到集合Si.記Si是前i次查詢中敵手沒有的元素對應(yīng)的Π的輸出.顯然Si和OΠ是不相交的，所以計算K為

K={H2(y,e(Π(Q(H1(y))),cP)b)|

y∈YandQ(H1(y))?Si}.

最后在K中加入隨機元素，直到|K|=n.

此后，hybrid2,i+1將hybrid2,i中的e(Π(Q(H1(y))),cP)b替換為隨機值.根據(jù)DBDH假設(shè)可知，hybrid2,i+1和hybrid2,i是無法區(qū)分的.

4)hybrid3.重寫了hybrid2,q，所有Π(f)=m都用Sq和OΠ表示，對于所有滿足Π(f)=m的值必然屬于這2個集合的其中之一，即Q(H1(y))?Si等價于Q(H1(y))∈OΠ，因此K可以表示為

K={H2(y,e(Π(Q(H1(y))),cP)b)|

y∈YandQ(H1(y))∈OΠ}.

由hybrid1已知，若存在任何y?O1但Q(H1(y))∈OΠ，則交互將終止.這意味著Q(H1(y))∈OΠ隱含著y∈O1.因此，K可以進一步改寫為

K={H2(y,e(Π(Q(H1(y))),cP)b)|

y∈Y∩O1andQ(H1(y))∈OΠ}.

5)hybrid4.hybrid3基礎(chǔ)上，誠實的參與方B查詢H2以獲得K.若一個H2查詢是第1次查詢，但結(jié)果在O2中，則協(xié)議終止.此類事件的概率是|O2|/|F|=n/|F|，是可以忽略的，則hybrid4與hybrid3是無法區(qū)分.

假設(shè)hybrid4維護了前面描述的列表O2，即(y,e(Π(Q(H1(y))),cP)b,k′)∈O2意味著敵手查詢H2(y,e(Π(Q(H1(y))),cP)b)并得到輸出密鑰的隨機預(yù)言機查詢結(jié)果.由于參與者B只識別敵手已經(jīng)向H2查詢過的值，因此hybrid4可以寫作：

K={k′|(y,e(Π(Q(H1(y))),cP)b,k′)∈O2|

y∈Y∩O1andQ(H1(y))∈OΠ}.

K={H2(y,e(Π(Q(H1(y))),cP)b)|

此時，hybrid4與模擬器的行為是相同的.

綜上，模擬協(xié)議和真實協(xié)議是不可區(qū)分的，從而證明了在惡意參與方A,C合謀的情況下，協(xié)議2安全地實現(xiàn)了隱私交集計算功能.

證畢.

定理4.假設(shè)H1,H2是隨機預(yù)言機，Π,Π-1是理想置換，則協(xié)議2在惡意參與方A,B合謀的情況下安全性歸約于判定性雙線性問題的困難性假設(shè).

證明.首先刻畫模擬器S的能力：

1)S扮演隨機預(yù)言機H1,H2和理想置換Π±的角色同定理3.

2)在收到多項式Q(·)之后，S定義集合

3)在接收到來自敵手的K后，S定義集合

k′)∈O2andk′∈K}.

以下通過混合序列hybridh，證明了這個模擬協(xié)議與真實協(xié)議是無法區(qū)分的.

1)hybrid0.這是真實的交互，合謀方A,B與參與方C按照協(xié)議規(guī)則運行，交集可以表示為

{z∈Z|H2(z,e(Π(Q(H1(z))),bP)c)∈K},

同時，列表O1,O2和OΠ也被生成.

2)hybrid1.與hybrid0唯一的不同是：Π±的模擬.所有對Π和Π-1的新查詢都以隨機值進行響應(yīng).若Π或Π-1獲得重復(fù)的輸出，則交互將終止.因此hybrid1與hybrid0是無法區(qū)分的.

3)hybrid2.與hybrid1不同是：若存在z∈Z滿足z?O1但Q(H1(z))∈OΠ，則交互終止，即敵手從未查詢H1(z)，但Q(H1(z))卻是它從Π-1輸出的值.這種概率是可忽略的.對于任意f∈OΠ，多項式等式Q(·)=f至多有n個解且在F中均勻分布，因此至少有n/|F|概率滿足Q(H1(z))=f.假設(shè)敵手對它的預(yù)言機做了總共q次查詢，通過n個z∈Z和q個f∈OΠ，總概率為n2q/|F|，這個概率也是可忽略的.若不終止，則意味著Q(H1(z))∈OΠ且z∈O1.因此輸出形式改寫為

{z∈Z|H2(z,e(Π(Q(H1(z))),bP)c)∈K

andQ(H1(z))∈OΠandz∈O1}.

4)hybrid3.誠實的接收者查詢H2以獲得輸出，與hybrid2唯一的不同是H2如何模擬.若H2查詢是第1次被查詢但結(jié)果卻在K中，則協(xié)議終止.此類事件的概率是|K|/|F|=n/|F|，這是可忽略的，因此hybrid3與hybrid2無法區(qū)分.

假設(shè)hybrid3維護了列表O2，即(z,e(Π(Q(H1(z))),bP)c,k′)∈O2意味著敵手查詢H2(z,e(Π(Q(H1(z))),bP)c)并得到結(jié)果k′.由于C識別敵手已經(jīng)向H2查詢過的值，可記作：

{z∈Z|?k′:(z,e(Π(Q(H1(z))),bP)c,k′)∈

O2andk′∈KandQ(H1(z))∈OΠandz∈O1},

等價于：

Z∩{x|?k′:(x,e(Π(Q(H1(x))),bP)c,k′)∈

O2andk′∈KandQ(H1(x))∈OΠandx∈O1}.

Z∩{x|x∈O1andQ(H1(x))∈OΠ}∩

{y|?k′:(y,e(Π(Q(H1(y))),bP)c,k′)∈

O2andk′∈K}.

綜上，模擬器的行為和真實協(xié)議是不可區(qū)分的，從而證明了在惡意參與方A,B合謀的情況下，協(xié)議2依然安全地實現(xiàn)了隱私交集計算功能.

證畢.

4 協(xié)議性能與比較

4.1 實驗環(huán)境與參數(shù)

本文使用C++實現(xiàn)了基于密鑰協(xié)商的三方惡意隱私集合交集計算協(xié)議，并與同類方案進行了對比.實驗環(huán)境為:Ubuntu 18.04.4 LTS, Intel?CoreTMi7-8750H CPU @2.20 GHz, 16 GB RAM.實驗中采用帶有固定密鑰且分組長度為128 b的AES算法作為理想置換，并使用SHA2實例化必要的哈希函數(shù).具體實現(xiàn)中采用了libOTe庫以及l(fā)ibsodium庫，最后利用PBC庫提供的A類曲線(y2=x3+x)實現(xiàn)了雙線性配對.所有計算均采用PSI元素長度為128 b，計算安全參數(shù)κ=128，統(tǒng)計安全參數(shù)λ=40.

4.2 性能評估與分析

小集合場景下的性能：本文分別對各參與方集合元素數(shù)量為24,25,26,27,28,29這6種情況對惡意隱私集合交集協(xié)議進行了仿真實驗測試.

在實施過程中，協(xié)議的計算成本包括：參與方B和參與方C計算bP和cP，以及n個經(jīng)過雙線性運算的密鑰輸出；參與方A計算n個aiP.3個參與方對H1和Π±各進行n次查詢；參與方B和C分別對H2進行n次查詢；最后參與方A必須插值一個多項式，參與方B，C在n個點上對多項式求值，這都需要O(nlb2n)個域操作[41].由參與方C進行對比得出交集，各個參與方負(fù)載均衡.該協(xié)議的總通信成本包括：參與方B，C發(fā)送的bP和cP；用于描述多項式Q(·)的n個域元素；n個H2輸出，每個2κ位.

表1展示了本文提出的惡意三方PSI協(xié)議的通信量和各階段運行時間.本文的協(xié)議適合預(yù)計算，可將部分計算放在離線階段進行.在實驗測試性能時，本文將協(xié)議分為離線階段和在線階段：離線階段主要是參數(shù)的生成以及參與方A的多項式插值的計算；在線階段各方交互并得出交集.耗時為在線階段和離線階段的運行時間，通信量為所有參與方發(fā)送/接收數(shù)據(jù)的總和.從實驗數(shù)據(jù)可以看出，本文提出的協(xié)議十分適用于參與方所具有的集合元素較少的情況.在集合元素較少的情況下，該協(xié)議具有較高的運算效率和極低的通信量；在集合元素較多的情況下，由于本文協(xié)議涉及雙線性配對計算，所以效率有所下降。對比已有三方PSI協(xié)議，本文協(xié)議仍具有最高的通信效率。因此，本文協(xié)議適用于網(wǎng)絡(luò)帶寬和通信量均受限的場景.

Table 1 Communication and Running Time of Our Protocol in Small Set Scenarios

4.3 性能對比

表2展示了本文方案與相關(guān)工作的綜合對比.其中n是集合中元素的個數(shù).表2中的文獻都可以實現(xiàn)三方PSI的計算.本文提出的方案分別提供了半誠實和惡意安全性，并且在任意兩方合謀時都是安全的.此外，本文在2種安全模型下都實現(xiàn)了線性的通性復(fù)雜度和計算復(fù)雜度并且僅需要兩輪通信交互.文獻[31]、文獻[43]以及文獻[42]可提供半誠實的安全性.相比之下，本文協(xié)議的半誠實版本具有更低的通信輪數(shù)以及通信復(fù)雜度和計算復(fù)雜度，并允許任意兩方合謀.

Table 2 Comparison of Related Semi-Honest and Malicious Three-Party PSI Protocols

文獻[32,35,42,44-45]都可以在惡意敵手存在的情況下完成工作.文獻[45]表明必須有指定的2個服務(wù)器是不合謀的，所以文獻[45]在三方交集中存在兩方合謀時是不安全的.文獻[42]基于加法同態(tài)加密框架構(gòu)建，且在惡意版本的協(xié)議中需要O(n2)計算復(fù)雜度，其未提供任何實驗數(shù)據(jù)和代碼，但預(yù)計其效率要比本文低的多.文獻[44]基于不經(jīng)意線性函數(shù)評估(oblivious linear function evaluation, OLE)構(gòu)建，同樣需要大量公鑰操作，其優(yōu)勢在于通信量較低，當(dāng)集合包含216個元素時，有固定通信量為80 MB，這是本文通信量的8倍.文獻[32]和文獻[35]均基于高效的OT擴展，具有較高的運算效率，主要瓶頸均在于通信.

大集合場景下相關(guān)方案的通信量對比：文獻[32]和文獻[35]與本文在3個參與方，各參與方集合大小為28,212,216,220，且存在合謀情況下的通信量對比如表3所示.可以看出，擁有相同的集合大小時，相比于文獻[32]和文獻[35]，本文方案的通信量降低了89%～98%.因此，本文的協(xié)議也將適用于此類具有較大集合(210～220個元素)且需要降低通信量的場景中.例如在集合大小是220時，文獻[32]和文獻[35]通信開銷分別約為20 GB和1.6 GB，這在通信帶寬受限的場景中是不可接受的.

Table 3 Communication Comparison of Malicious Secure Three-Party PSI Protocol in Large Set Scenarios

小集合場景下相關(guān)方案的對比：基于同態(tài)加密的方案同樣適應(yīng)于弱通信場景，具有較低通信量，但由于需要大量公鑰加密操作，計算速度比本文方案慢幾個數(shù)量級.文獻[25]與文獻[26]均基于同態(tài)加密實現(xiàn)了多方PSI，這2個文獻與本文方案的通信量和運行時間對比如圖4所示.由圖4可知，文獻[26]的通信量和運行時間都很高，這與其采用同態(tài)加密的布隆過濾器有關(guān)；文獻[25]通信量較低，與本文基本相同，但其總運行時間是本文的10～25倍.

5 結(jié) 論

PSI協(xié)議是安全多方計算的重點研究問題之一.本文提出了2個基于密鑰協(xié)商的三方隱私集合交集計算協(xié)議，分別可以抵抗半誠實和惡意敵手且允許任意兩方合謀，通過模擬范式證明了方案的安全性.與現(xiàn)有方案相比，本文的方案具有較低的通信代價和更高的安全性，尤其適用于帶有小集合的三方隱私集合交集計算場景.在未來的工作中，我們將考慮進一步提高計算效率并擴展到普適多方的場景，一種可能的優(yōu)化是通過尋找不同的編碼方式以降低多項式插值過程的計算成本.

作者貢獻聲明：張蕾負(fù)責(zé)論文思路構(gòu)建和框架設(shè)計；賀崇德負(fù)責(zé)撰寫論文和實驗；魏立斐提出指導(dǎo)意見并負(fù)責(zé)論文校對與修訂.