摘 要：概率門限隱私集合交集研究作為門限隱私集合交集的一種概率變體，在指紋或人臉識(shí)別、聯(lián)邦學(xué)習(xí)等領(lǐng)域比確定型門限隱私集合交集協(xié)議效率更高。然而現(xiàn)有的概率門限隱私集合交集協(xié)議缺少針對(duì)惡意模型下的多方概率門限隱私集合交集的研究。針對(duì)該問(wèn)題，提出了兩種在惡意模型下安全的多方概率門限隱私集合交集協(xié)議。第一個(gè)多方概率門限隱私集合交集協(xié)議在參與方之間沒(méi)有合謀行為時(shí)，能夠抵御任意惡意敵手，并且使用對(duì)稱密鑰源語(yǔ)高效地實(shí)現(xiàn)了協(xié)議。該協(xié)議在八個(gè)參與方的場(chǎng)景下，集合大小為220，門限值為0.5 n，協(xié)議的時(shí)間成本約為24.59 s。此外，在第一個(gè)協(xié)議的基礎(chǔ)上結(jié)合零共享方案以及不經(jīng)意可編程偽隨機(jī)函數(shù)設(shè)計(jì)了一種抗合謀版本的協(xié)議，即當(dāng)兩個(gè)指定參與方不同時(shí)參與合謀時(shí)，該協(xié)議可以抵抗任意參與方子集進(jìn)行合謀攻擊。在相同實(shí)驗(yàn)設(shè)置下，當(dāng)合謀參與方數(shù)量為N/2時(shí)，協(xié)議的時(shí)間成本約為40.00 s。與現(xiàn)有方案的實(shí)驗(yàn)對(duì)比可得，該協(xié)議具有更多的應(yīng)用場(chǎng)景與更好的效率。

關(guān)鍵詞：概率門限隱私集合交集；不經(jīng)意鍵值對(duì)存儲(chǔ)；惡意安全；不經(jīng)意可編程偽隨機(jī)函數(shù)

中圖分類號(hào)：TP309"" 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）12-042-3834-09

doi： 10.19734/j.issn.1001-3695.2024.01.0109

Multiparty probabilistic threshold private set intersection method against malicious adversaries

Gong Yide， Zhang En， Wang Mengtao

（College of Computer amp; Information Engineering， Henan Normal University， Xinxiang Henan 453007， China）

Abstract：As a probabilistic variant of threshold private set intersection， probabilistic threshold private set intersection research is more efficient than deterministic threshold private set intersection protocol in fingerprint or face recognition， federated learning and other fields. However， the existing probabilistic threshold private set intersection protocols lack of research on multi-party probabilistic threshold private set intersection protocols under the malicious model. To address this problem， this paper proposed two multi-party probabilistic threshold private set intersection protocols that were secure under the malicious model. The first multi-party probabilistic threshold private set intersection protocol could resist any malicious adversary when there was no collusion among the participants， and it was efficiently implemented by using symmetric key primitives. In the setting of eight parties， the set size was 220， the threshold value was 0.5n， and the time cost of the protocol was about 24.59. In addition， on the basis of the first protocol，it designed a collusion-resistant version of the protocol" by combining the zero-sharing scheme and the obliviously programmable pseudo-random function. That was， when the two designated parties did not participate in collusion at the same time， the protocol could resist the collusion attack of any subset of participants. Under the same experimental setting， when the number of colluding parties was N/2， the time cost of the protocol was about 40.00 s. Compared with the existing schemes， the proposed protocol has more application scenarios and better efficiency.

Key words：probabilistic threshold private set intersection; oblivious key-value stores; malicious security; oblivious programmable pseudorandom function

0 引言

隱私集合交集（private set intersection，PSI）[1～9]是安全多方計(jì)算的一個(gè)變體，其允許各個(gè)參與方計(jì)算彼此集合之間的交集，而不泄露自己的私有信息。PSI在僵尸網(wǎng)絡(luò)檢測(cè)、模式匹配和人類基因組測(cè)試等領(lǐng)域廣泛應(yīng)用。然而在某些特定的場(chǎng)合，標(biāo)準(zhǔn)的PSI方案并不適用。例如，在基于隱私保護(hù)的數(shù)據(jù)挖掘中[10]，隱私數(shù)據(jù)在不同客戶端之間垂直分布，只有當(dāng)公共數(shù)據(jù)集合元素達(dá)到一定數(shù)量時(shí)，各方才希望獲得交集并繼續(xù)合作。在另一個(gè)保護(hù)用戶隱私的共享拼車案例中陌生人之間的路線在正常情況下不一定完全相同。為了保護(hù)他們的隱私，各方都不愿意與對(duì)方分享他們的路線。因此，僅當(dāng)用戶有更多的公共路線時(shí)，他們才會(huì)接受與他人拼車。

Freedman等人[11]提出了門限隱私集合交集（threshold private set intersection，TPSI）的概念，但他們沒(méi)有設(shè)計(jì)具體協(xié)議。門限隱私集合交集要求在參與方不泄露隱私且只有通過(guò)達(dá)到指定門限值（threshold）的前提下，才可以得到集合交集的結(jié)果。門限隱私集合交集技術(shù)在醫(yī)療行業(yè)中基因測(cè)序?qū)Ρ然蛲ㄟ^(guò)社交平臺(tái)搜索潛在用戶等多個(gè)領(lǐng)域存在廣泛應(yīng)用。該協(xié)議在提供了數(shù)據(jù)分析的同時(shí)保護(hù)了用戶的隱私。至此，針對(duì)TPSI的研究開(kāi)始逐漸深入[12～18]。

2019年，Ghosh等人[13]研究了具有次線性開(kāi)銷的兩方TPSI協(xié)議，并對(duì)TPSI的通信復(fù)雜度的上界進(jìn)行了討論。2018年，Boneh等人[19]提出了基于加性全同態(tài)加密的多方交集基數(shù)測(cè)試功能以及一個(gè)多方TPSI協(xié)議，但該協(xié)議仍處于理論研究階段，尚未進(jìn)行有效實(shí)現(xiàn)。Zhao等人[12]設(shè)計(jì)了一種交集大小大于門限輸出交集的協(xié)議和一種當(dāng)交集大小小于門限值時(shí)輸出交集的協(xié)議，通過(guò)利用同態(tài)加密以及多項(xiàng)式插值來(lái)實(shí)現(xiàn)這兩種TPSI協(xié)議，并且不會(huì)泄露交集大小。Badrinarayanan等人[14]拓展了文獻(xiàn)[13]，在此基礎(chǔ)上研究了多方TPSI的通信上界問(wèn)題。在該協(xié)議中，設(shè)計(jì)了兩個(gè)基于閾值同態(tài)加密的多方TPSI協(xié)議，其通信復(fù)雜度隨著集合差值的增加而增加。一種是交集元素與各個(gè)參與方集合元素之間的差集不大于門限時(shí)的輸出交集。另一種是當(dāng)交集元素與參與方集合并集之間的差集不大于門限時(shí)的輸出交集。

Branco等人[15]提出了一種基于多項(xiàng)式插值和遺忘矩陣乘法的集合大小測(cè)試協(xié)議，其主要功能是判斷各方隱私集合的交集大小是否≥n－t。類似于Badrinarayanan等人[14]的協(xié)議，該協(xié)議也將Ghosh等人[13]的協(xié)議從兩方擴(kuò)展到多方場(chǎng)景。該方案使用門限加法同態(tài)公鑰加密系統(tǒng)代替文獻(xiàn)[13]中的OLE，提出的多方TPSI協(xié)議的通信復(fù)雜度為O（ntk）。但在部分應(yīng)用場(chǎng)景中，門限隱私集合交集協(xié)議可能并不是最佳方案，如在大數(shù)據(jù)集合場(chǎng)景下的垂直聯(lián)邦學(xué)習(xí)中，當(dāng)交集大小|Euclid Math OneTAp|=t－1仍有助于協(xié)作訓(xùn)練模型，但標(biāo)準(zhǔn)的門限隱私集合交集協(xié)議并不支持這種情況，因此概率門限隱私集合交集協(xié)議應(yīng)運(yùn)而生。

2023年，張恩等人[17]提出了基于彈性秘密共享的多方門限隱私集合交集協(xié)議，該論文設(shè)計(jì)一種新的布隆過(guò)濾器構(gòu)造方法，并結(jié)合彈性秘密共享提出兩種有效的多方門限隱私集合交集協(xié)議，首次在半誠(chéng)實(shí)模型下仿真實(shí)現(xiàn)。在此之后，Liu等人[20]提出了概率門限隱私集合交集（probabilistic threshold private set intersection，pTPSI）的概念，概率門限隱私集合交集是標(biāo)準(zhǔn)門限隱私集合交集的概率變體。這種概率變體產(chǎn)生有效的設(shè)計(jì)并具有安全性。該變體類似于隨機(jī)算法，其中算法可能會(huì)以一定的概率去計(jì)算交集基數(shù)，但在性能方面可以明顯優(yōu)于確定性的對(duì)應(yīng)方法。例如，在垂直聯(lián)邦學(xué)習(xí)中，只有當(dāng)不同計(jì)算方有足夠多的普通用戶（或某種更通用的id）時(shí)，才可能開(kāi)始合作（訓(xùn)練模型）。并且，在大型數(shù)據(jù)集（例如220）的設(shè)置中，通常不清楚如何定義集合交集的輸出條件，只是簡(jiǎn)單地設(shè)置一個(gè)確定門限值t。也許當(dāng)交集大小|Euclid Math OneTAp|=t－1時(shí)，仍然有助于各方協(xié)作訓(xùn)練模型，但TPSI不支持這種情況。因此，概率性門限更適合這種情況。他們?cè)O(shè)計(jì)了一個(gè)高效的多方概率集合大小測(cè)試協(xié)議，實(shí)現(xiàn)了Euclid Math OneFAppSize-Test的一些功能，將經(jīng)典的Goldwasser-Sipser[21]（GS）協(xié)議推廣到多方變體，以降低集合交集的大小。

同時(shí)利用Euclid Math OneFAppSize-Test和任何高效的PSI協(xié)議，在半誠(chéng)實(shí)模型下高效地實(shí)現(xiàn)Euclid Math OneFAppTPSI。此外，通過(guò)結(jié)合特定的基于OPRF的PSI協(xié)議[3]，實(shí)現(xiàn)了一個(gè)高效的惡意安全概率（兩方）TPSI版本，該版本可以很好地與概率集合大小的測(cè)試協(xié)議混合。

然而他們的研究?jī)H實(shí)現(xiàn)了半誠(chéng)實(shí)模型下的多方pTPSI以及惡意模型下的兩方pTPSI方案，目前仍缺少更貼近現(xiàn)實(shí)條件下的多方惡意模型下的pTPSI實(shí)現(xiàn)方案。

綜上所述，本文針對(duì)惡意模型下的多方pTPSl研究，構(gòu)造了兩個(gè)多方pTPSI協(xié)議，且本文協(xié)議具有以下優(yōu)勢(shì)：

a）首次實(shí)現(xiàn)了惡意模型下的多方pTPSI協(xié)議。

b）設(shè)計(jì)了一種無(wú)合謀pTPSI協(xié)議，該協(xié)議基于對(duì)稱密鑰源語(yǔ)，具有更高的工作效率。

c）結(jié)合零異或思想以及不經(jīng)意鍵值對(duì)存儲(chǔ)設(shè)計(jì)了第二個(gè)有效的多方pTPSI協(xié)議，實(shí)現(xiàn)了當(dāng)參與方數(shù)量為N個(gè)時(shí)，且在兩個(gè)指定參與方不同時(shí)參與合謀的前提下，該方案可以抵抗至多N－1個(gè)參與方進(jìn)行合謀。

d）本文提出的無(wú)合謀協(xié)議在八個(gè)參與方的場(chǎng)景下，集合大小為220，門限值為0.5n時(shí)（n為集合元素?cái)?shù)量），協(xié)議的時(shí)間成本約為24.59 s。在改進(jìn)的抗合謀協(xié)議中，相同條件下，當(dāng)合謀參與方數(shù)量為N/2時(shí)，協(xié)議的時(shí)間成本約為40.00 s。

1 基礎(chǔ)知識(shí)

1.1 多方門限隱私集合交集

多方門限隱私集合交集協(xié)議，是指N個(gè)參與方在不泄露自己隱私集合信息的前提下得到參與方之間的集合交集信息。本文定義了具有多個(gè)參與方的隱私集合交集的理想函數(shù)Euclid Math OneFApPSI如下：

參數(shù)：N個(gè)參與方，每個(gè)參與方集合大小n。

輸入：每個(gè)參與方Pi輸入其集合Xi={xi1，…，xin}。

輸出：輸出交集|∩Ni=1xi。

定義了惡意模型下的多方門限隱私集合交集Euclid Math OneFApTPSI的理想函數(shù)如下：

參數(shù)：N個(gè)參與方，每個(gè)參與方集合大小的上限為n，門限值為T。

輸入：每個(gè)參與方Pi輸入其集合Xi={xi1，…，xin}。

輸出：如果|∩Ni=1Xi|≥T，則輸出交集∩Ni=1Xi，否則輸出⊥。

1.2 安全模型

在惡意模型中，敵手可以任意行動(dòng)。這種安全性是通過(guò)一個(gè)理想的過(guò)程來(lái)形式化的，這個(gè)過(guò)程涉及到一個(gè)可靠的第三方。雙方將其輸入發(fā)送給可信方?？尚欧接?jì)算輸入的功能，并發(fā)回輸出。如果真實(shí)協(xié)議中的任何敵手都可以被理想模型中的敵手模擬，則稱該協(xié)議是安全的。

在本文中，通過(guò)使用Canetti[22]的通用可組合性（UC）框架來(lái)證明本文協(xié)議的安全性。本文假設(shè)存在一個(gè)靜態(tài)的、惡意的敵手，它可能破壞t個(gè)參與方（除一方之外的所有參與方），敵手完全控制這些參與方，并可以指示他們?nèi)我馄x規(guī)定的執(zhí)行協(xié)議。與此同時(shí)，假設(shè)所有參與方都通過(guò)安全的點(diǎn)對(duì)點(diǎn)通道連接，且各方都可以訪問(wèn)（同一個(gè)）全局隨機(jī)預(yù)言機(jī)（也就是說(shuō)，同一個(gè)預(yù)言機(jī)也可以用于其他協(xié)議的執(zhí)行）。

3.2 安全證明

定理4 本文2.2節(jié)的協(xié)議針對(duì)惡意敵手不同時(shí)破壞Pv或Pn且存在最多N－1個(gè)合謀方的情況下，安全地實(shí)現(xiàn)了πpSize-Test、FF，n，mzeroXOR與隨機(jī)預(yù)言機(jī)混合模型下理想函數(shù)Euclid Math OneFAppTPSI的功能。

該協(xié)議在Pv或Pn同時(shí)被惡意敵手破壞時(shí)，即{Pv，Pn}∈Euclid Math OneCAp時(shí)，存在一定的安全隱患。在這種情況下，Pv和Pn可以在協(xié)議步驟g）通過(guò)合謀手段跳過(guò)πpSize-Test協(xié)議的門限測(cè)試，這也意味著即使交集基數(shù)沒(méi)有達(dá)到門限值，合謀方仍然可以獲得交集。

但該協(xié)議在面對(duì)合謀時(shí)仍然提供了有意義的安全保證，并不是失去所有的安全性。在最多N－1方串通的情況下，該協(xié)議只允許惡意敵手了解輸入集交集之外的任何信息。

證明 為了提取該方案腐敗參與方的輸入，模擬器首先模擬參與方Pi的視圖。對(duì)于Pi對(duì)隨機(jī)預(yù)言機(jī)的每次調(diào)用結(jié)果H（x），模擬器將其x輸入到列表T中。類似2.3節(jié)的證明，參與方Pi將發(fā)送計(jì)算的OKVS Si給Pv或者發(fā)送鍵值對(duì)集合Xi到FF，t+1，mzeroXOR中，模擬器可以因此計(jì)算出參與方的實(shí)際有效輸入。

本文將被惡意敵手A破壞的參與方集合或單個(gè)參與方表示為Euclid Math OneCAp。

4 實(shí)驗(yàn)與分析

本文分別針對(duì)無(wú)合謀和惡意敵手不同時(shí)破壞Pv或Pn的任意合謀的情況設(shè)計(jì)了2.2節(jié)和3.2節(jié)的協(xié)議，協(xié)議的實(shí)現(xiàn)使用了文獻(xiàn)[24，27]中的惡意OPPRF代碼以及基于Paxos數(shù)據(jù)結(jié)構(gòu)[24]中的編解碼算法，并將實(shí)驗(yàn)結(jié)果與最近的相關(guān)論文實(shí)驗(yàn)結(jié)果進(jìn)行了比較。

該論文協(xié)議的實(shí)現(xiàn)使用C++語(yǔ)言，并在Ubuntu 18.04的系統(tǒng)中進(jìn)行仿真實(shí)驗(yàn)，其中CPU為32核Intel Xeon 2.0GHz （E5-2620）以及32 GB RAM。協(xié)議的計(jì)算安全參數(shù)設(shè)置為λ=128，統(tǒng)計(jì)安全參數(shù)σ=40，并使用MP-SPDZ庫(kù)實(shí)現(xiàn)函數(shù)Euclid Math OneFAp∩-count。

4.1 計(jì)算與通信復(fù)雜度

本節(jié)首先針對(duì)2.2節(jié)中無(wú)合謀協(xié)議的計(jì)算復(fù)雜度進(jìn)行分析，該協(xié)議提出了在無(wú)合謀（t=1）的情況下通過(guò)將n方pTPSI問(wèn)題簡(jiǎn)化為兩方pTPSI，其中參與方P1在協(xié)議執(zhí)行過(guò)程中需要計(jì)算一個(gè)OKVS，其計(jì)算復(fù)雜度與集合元素以及參與方數(shù)量相關(guān)，為O（nm）。參與方Pi（i∈{2，…，n－2}）分別針對(duì)m個(gè)集合元素計(jì)算一個(gè)OKVS，Pn－1方解碼接收到的O（n）個(gè)OKVS實(shí)例，其中每個(gè)實(shí)例都需要在O（m）個(gè)值上進(jìn)行計(jì)算，因此計(jì)算復(fù)雜度為O（nm）。參與方Pn根據(jù)O（m）的值解碼單個(gè)OKVS。最后在πpSize-Test階段中的計(jì)算復(fù)雜度為O（k log m+m+Nk）?？紤]到通信復(fù)雜度分析，每個(gè)參與方Pi（i∈{1，…，n－2}）發(fā)送一個(gè)使用O（m）個(gè)值進(jìn)行編碼的OKVS集合。與此同時(shí)，參與方P1與Pn－1分別發(fā)送O（n）個(gè)κ位長(zhǎng)的密鑰以及O（m）的解碼集合。最后兩方在πpSize-Test階段中的通信復(fù)雜度為O（Nm+λ）。

本文將3.2節(jié)抗合謀攻擊的多方pTPSI協(xié)議的計(jì)算復(fù)雜度分為三種角色進(jìn)行分析。客戶端的計(jì)算復(fù)雜度與集合大小m以及合謀方的數(shù)量t成比例，因?yàn)槊總€(gè)客戶端Pi（i∈［v－1］）需要基于所有t個(gè)密鑰kji（j∈［v+1，n］）來(lái)計(jì)算生成對(duì)應(yīng)的OKVS。其中單個(gè)OKVS需要從每個(gè)客戶端發(fā)送到中樞方，因此客戶端的通信復(fù)雜度與集合元素?cái)?shù)量m相關(guān)，為O（m）。

中樞方的計(jì)算復(fù)雜度取決于n－t，因?yàn)樵搮⑴c方負(fù)責(zé)解碼來(lái)自每個(gè)客戶端的OKVS。因此，中樞方的通信和計(jì)算復(fù)雜度為O（m（n－t））。

服務(wù)器僅接收了來(lái)自客戶端的密鑰，該密鑰并不依賴于集合大小，且這些參與方的計(jì)算是針對(duì)每個(gè)項(xiàng)目每個(gè)鍵進(jìn)行PRF計(jì)算。此外，該服務(wù)器方參與了零異或協(xié)議，該協(xié)議為除了Pn之外的所有參與方在m中產(chǎn)生了線性開(kāi)銷。而Pn參與了t－1個(gè)OPPRF實(shí)例的調(diào)用。因此，對(duì)于服務(wù)器Pi（i∈［v+1，n－1］）的計(jì)算和通信復(fù)雜度為O（m（n－t））和O（m），Pn的計(jì)算和通信復(fù)雜度為O（m（n－t））和O（m（t－1））。其中該協(xié)議中πpSize-Test階段的計(jì)算和通信復(fù)雜度仍為O（k log m+m+Nk）和O（Nm+λ）。

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

本節(jié)首先測(cè)試πpSize-Test協(xié)議的具體效率，為了實(shí)現(xiàn)（α，β）-pTPSI協(xié)議，本文設(shè)置β=T和α=T/2，其中T為pTPSI的門限值，并且本文設(shè)置T=0.5n。由于πpSize-Test協(xié)議由GS階段和使用SPDZ實(shí)現(xiàn)的Euclid Math OneFAp∩-count子例程階段組成，所以首先分別測(cè)試這兩個(gè)階段的運(yùn)行時(shí)間，然后給出πpSize-Test協(xié)議的總體時(shí)間成本。設(shè)置輸入元素的長(zhǎng)度m=128，線程數(shù)為32，對(duì)于不同的k值（GS協(xié)議要求的并行重復(fù)次數(shù)），設(shè)置七個(gè)級(jí)別為5 000～8 000。其中表1為GS階段的時(shí)間成本，表2為Euclid Math OneFAp∩-count子例程階段的時(shí)間成本，表3為πpSize-Test協(xié)議的總體運(yùn)行時(shí)間成本。

針對(duì)第3章中的無(wú)合謀多方pTPSI，首先固定參與方集合數(shù)量為220時(shí)，設(shè)置不同大小的k值以及參與方數(shù)量。該協(xié)議時(shí)間成本如表4所示。然后固定k值為8 000，設(shè)置不同的參與方數(shù)量以及集合元素?cái)?shù)量。該協(xié)議時(shí)間成本如表5所示，通信開(kāi)銷如表6所示。

針對(duì)抗合謀多方pTPSI，固定合謀方數(shù)量為N/2，其運(yùn)行時(shí)間如表7和8所示。通信開(kāi)銷如表9所示。

本文與相關(guān)文獻(xiàn)的對(duì)比實(shí)驗(yàn)結(jié)果如表10所示。由于本文是首個(gè)實(shí)現(xiàn)的惡意模型下的多方pTPSI協(xié)議，目前尚未找到可以與之對(duì)比的惡意模型下多方pTPSI協(xié)議，所以本文將與目前半誠(chéng)實(shí)環(huán)境下可實(shí)現(xiàn)的TPSI協(xié)議的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對(duì)比，其中文獻(xiàn)[17]為多方TPSI協(xié)議，其余兩篇為兩方TPSI協(xié)議。由實(shí)驗(yàn)數(shù)據(jù)可知，本文協(xié)議設(shè)置在10個(gè)參與方且集合元素大小為211時(shí)進(jìn)行比較，其總體運(yùn)行時(shí)間大約是文獻(xiàn)[18，28]的1/220，在集合元素大小為228時(shí)，總體運(yùn)行時(shí)間大約為文獻(xiàn)[17]的1/15。

為了更清晰地展現(xiàn)本文兩種協(xié)議之間功能與效率的對(duì)比，圖3、4為設(shè)置在八個(gè)參與方且固定合謀方數(shù)量為N/2時(shí)兩種協(xié)議的運(yùn)行時(shí)間以及通信開(kāi)銷的對(duì)比。由圖3和4可知，無(wú)合謀pTPSI協(xié)議在實(shí)驗(yàn)效率上更具優(yōu)勢(shì)，而抗合謀pTPSI協(xié)議的安全性更高。

5 結(jié)束語(yǔ)

本文在惡意模型下提出并實(shí)現(xiàn)了兩種多方pTPSI協(xié)議，并在惡意模型下證明了協(xié)議的安全性。該協(xié)議可以解決多方場(chǎng)景下大型數(shù)據(jù)集的門限隱私集合求交問(wèn)題，同時(shí)可以減少因準(zhǔn)確閾值造成不必要的額外開(kāi)銷。本文的第一個(gè)協(xié)議在無(wú)合謀參與方的場(chǎng)景下，通過(guò)使用對(duì)稱密鑰源語(yǔ)實(shí)現(xiàn)了多參與方大數(shù)據(jù)集情況下高效的pTPSI。第二個(gè)協(xié)議通過(guò)結(jié)合多方零異或以及不經(jīng)意可編程偽隨機(jī)函數(shù)實(shí)現(xiàn)了在惡意敵手不同時(shí)破壞特定方的情況下，至多可以抵抗N-1個(gè)參與方合謀。分析表明以上兩種協(xié)議都可以有效防止交集基數(shù)泄露問(wèn)題。在以后的工作中仍需在惡意模型下針對(duì)如何抵抗任意參與方合謀的行為進(jìn)行研究并改進(jìn)。

參考文獻(xiàn)：

[1]

Zhang En， Liu Fenghao， Lai Qiqi， et al.Efficient multi-party private set intersection against malicious adversaries [C]// Proc of ACM SIGSAC Conference on Cloud Computing Security Workshop. New York：ACM Press， 2019： 93-104.

[2]Garimella G， Pinkas B， Rosulek M， et al.Oblivious key-value stores and amplification for private set intersection [C]//Proc of the 41st Annual International Cryptology Conference. 2021： 395-425.

[3]Rindal P， Schoppmann P. VOLE-PSI： fast OPRF and circuit-PSI from vector-OLE [C]//Proc of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2021： 901-930.

[4]趙宗渠， 王書(shū)靜， 湯永利， 等. 基于理想格的兩方隱私集合交集協(xié)議 [J]. 計(jì)算機(jī)應(yīng)用研究， 2023， 40 （12）： 3795-3799. （Zhao Zongqu， Wang Shujing， Tang Yongli， et al.Two-party private set intersection protocol based on ideal lattice [J]. Application Research of Computers， 2023， 40 （12）： 3795-3799.）

[5]Bay A， Erkin Z， Hoepman J H， et al.Practical multi-party private set intersection protocols [J]. IEEE Trans on Information Forensics and Security， 2021， 17： 1-15.

[6]鞏林明， 王道順， 劉抹萌， 等. 基于無(wú)匹配差錯(cuò)的PSI計(jì)算 [J]. 計(jì)算機(jī)學(xué)報(bào)， 2020， 43 （9）： 1769-1790. （Gong Linming， Wang Daoshun， Liu Momeng， et al.PSI calculations based on no matching errors [J]. Chinese Journal of Computers， 2020， 43 （9）： 1769-1790.）

[7]楊佳輝， 陳蘭香， 穆怡， 等. 結(jié)構(gòu)化加密的PSI協(xié)議 [J]. 計(jì)算機(jī)學(xué)報(bào)， 2022， 45 （12）： 2652-2666. （Yang Jiahui， Chen Lanxiang， Mu Yi， et al.Efficient circuit-based PSI via cuckoo hashing [J]. Chinese Journal of Computers， 2022， 45 （12）： 2652-2666.）

[8]Raghuraman S， Rindal P. Blazing fast PSI from improved OKVS and subfield VOLE [C]// Proc of ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press， 2022： 2505-2517.

[9]Rindal P， Rosulek M. Improved private set intersection against malicious adversaries [C]//Proc of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham： Springer， 2017： 235-259.

[10]Mohassel P， Zhang Yupeng. SecureML： a system for scalable private-preserving machine learning [C]// Proc of IEEE Symposium on Security and Private. Piscataway，NJ：IEEE Press， 2017： 19-38.

[11]Freedman M J， Nissim K， Pinkas B. Efficient private matching and set intersection [C]//Proc of International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2004： 1-19.

[12]Zhao Yongjun，Chow S S M. Can you find the one for me？ [C]//Proc of Workshop on Private in the Electronic Society.2018： 54-65.

[13]Ghosh S， Simkin M. The communication complexity of threshold private set intersection [C]//Proc of Annual International Cryptology Conference. Berlin： Springer， 2019： 3-29.

[14]Badrinarayanan S， Miao Peihan， Raghuraman S， et al.Multi-party threshold private set intersection with sublinear communication [C]// Proc of International Conference on Public-Key Cryptography. Berlin： Springer， 2021： 349-379.

[15]Branco P， Dttling N， Pu S. Multiparty cardinality testing for threshold private intersection [C]//Proc of IACR International Conference on Public-Key Cryptography. Berlin： Springer， 2021： 32-60.

[16]Ghosh S， Simkin M. Threshold private set intersection with better communication complexity [C]//Proc of International Conference on Public-Key Cryptography. Berlin： Springer， 2023： 251-272.

[17]張恩， 秦磊勇， 楊刃林， 等. 基于彈性秘密共享的多方門限隱私集合交集協(xié)議 [J]. 軟件學(xué)報(bào)， 2023， 34 （11）： 5424-5441. （Zhang En， Qin Leiyong， Yang Renlin， et al.Threshold protocol for multi-party private set intersection based on resilient secret sharing [J]. Journal of Software， 2023， 34 （11）： 5424-5441.）

[18]Hallgren P， Orlandi C， Sabelfeld A. PrivatePool： private-preserving ridesharing [C]//Proc of the 30th IEEE Computer Security Foundations Symposium. Piscataway，NJ：IEEE Press， 2017： 276-291.

[19]Boneh D， Gennaro R， Goldfeder S， et al.Threshold cryptosystems from threshold fully homomorphic encryption [C]// Proc of the 38th Annual International Cryptology Conference. Berlin：Springer International Publishing， 2018： 565-596.

[20]Liu Fenghao， Zhang En， Qin Leiyong. Efficient multiparty probabilistic threshold private set intersection [C]// Proc of ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2023： 2188-2201.

[21]Goldwasser S， Sipser M. Private coins versus public coins in interactive proof systems [C]// Proc of the 18th Annual ACM Symposium on Theory of Computing. New York：ACM Press， 1986： 59-68.

[22]Canetti R. Universally composable security： a new paradigm for cryptographic protocols [C]// Proc of the 42nd IEEE Symposium on Foundations of Computer Science. Piscataway，NJ：IEEE Press， 2001： 136-145.

[23]Freedman M J， Ishai Y， Pinkas B， et al.Keyword search and obli-vious pseudorandom functions [C]// Proc of the 2nd Theory of Cryptography Conference on Theory of Cryptography. 2005： 303-324.

[24]Pinkas B， Rosulek M， Trieu N， et al.PSI from PaXoS： fast， malicious private set intersection [C]// Proc of Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2020： 739-767.

[25]Kolesnikov V， Matania N， Pinkas B， et al.Practical multi-party private set intersection from symmetric-key techniques [C]// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York：ACM Press， 2017： 1257-1272.

[26]Nevo O， Trieu N， Yanai A. Simple， fast malicious multiparty private set intersection [C]// Proc of ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press， 2021： 1151-1165.

[27]Damgrd I， Pastro V， Smart N， et al.Multiparty computation from somewhat homomorphic encryption [C]//Proc of Annual Cryptology Conference. Berlin： Springer， 2012： 643-662.

[28]Zhao Yongjun， Chow S S M. Are you the one to share？Secret transfer with access structure [EB/OL]. （2015）. https：//eprint.iacr.org/2015/929.pdf.

[29]Ghosh S， Nilges T. An algebraic approach to maliciously secure private set intersection [C]//Proc of Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2019： 154-185.

[30]Zhao Shengnan， Ma Ming， Song Xiangfu， et al.Lightweight threshold private set intersection via oblivious transfer [C]// Proc of the 16th International Conference on Wireless Algorithms， Systems， and App-lications. Berlin：Springer， 2021： 108-116.