抗惡意敵手的線(xiàn)性門(mén)限隱私集合交集協(xié)議

摘 要：門(mén)限隱私集合交集（TPSI）是安全多方計(jì)算中的一種特例，其在機(jī)器學(xué)習(xí)、共享拼車(chē)、指紋識(shí)別等多個(gè)領(lǐng)域有廣泛的應(yīng)用。然而，目前存在的方案均基于計(jì)算復(fù)雜度較高的算法，并且僅在半誠(chéng)實(shí)模型下實(shí)現(xiàn)，導(dǎo)致協(xié)議計(jì)算開(kāi)銷(xiāo)較大且無(wú)法抵抗惡意敵手的攻擊。為了解決以上問(wèn)題，首先提出了一個(gè)向量不經(jīng)意匹配測(cè)試（VOMT）協(xié)議，并基于VOMT和布谷鳥(niǎo)哈希設(shè)計(jì)了一個(gè)高效的半誠(chéng)實(shí)TPSI協(xié)議。此外，結(jié)合VOMT與對(duì)稱(chēng)密鑰加密方案構(gòu)造出向量不經(jīng)意解密匹配測(cè)試（VODMT）協(xié)議，并基于VODMT與不經(jīng)意偽隨機(jī)函數(shù)設(shè)計(jì)了一個(gè)可以抵抗惡意敵手的TPSI協(xié)議。隨后，分別在半誠(chéng)實(shí)模型和惡意模型下證明了協(xié)議的安全性，并分析得出兩個(gè)協(xié)議的計(jì)算復(fù)雜度和通信復(fù)雜度均為線(xiàn)性。在集合大小為4 096時(shí)，提出的兩個(gè)協(xié)議的在線(xiàn)運(yùn)行時(shí)間分別為0.81 s和1.81 s，而先前的工作則需要5 627 s，所以?xún)蓚€(gè)協(xié)議均是高效的。

關(guān)鍵詞：隱私計(jì)算； 門(mén)限隱私集合交集； 不經(jīng)意鍵值對(duì)存儲(chǔ)； 不經(jīng)意偽隨機(jī)函數(shù)； 布谷鳥(niǎo)哈希

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

文章編號(hào)：1001-3695（2024）09-039-2846-08

doi：10.19734/j.issn.1001-3695.2023.12.0601

Linear threshold private set intersection against malicious adversaries

Jia Zhengkuna， Zhang Ena，b， Wang Mengtaoa

（a.School of Computer & Information Engineering， b.Key Laboratory of Artificial Intelligence & Personalized Learning in Education of Henan Province， Henan Normal University， Xinxiang Henan 453007， China）

Abstract：Threshold private set intersection（TPSI） is a special case of secure multi-party computation， which is widely used in many fields such as machine learning， ride-sharing， and fingerprint recognition. However， currently existing solutions are all based on algorithms with high computational complexity and are only implemented under a semi-honest model， resulting in high computational overhead and inability to resist attacks by malicious adversaries. In order to solve the above problems， this paper first proposed a vector oblivious match test（VOMT） protocol and designed an efficient semi-honest TPSI protocol based on VOMT and cuckoo hashing. In addition， it combined VOMT and symmetric key encryption schemes to construct the vector oblivious decryption matching test（VODMT） protocol and designed a TPSI protocol based on VODMT and oblivious pseudo-random functions that could resist malicious adversaries. Subsequently， it proved the security of the protocol under the semi-honest model and the malicious model respectively， and analyzed that the computational complexity and communication complexity of the two protocols were linear. When the set size is 4 096， the online running time of the two proposed protocols is 0.81 s and 1.81 s respectively， while the previous work required 5 627 s， so both protocols are efficient.

Key words：private compute; threshold private set intersection; oblivious key-value stores; oblivious pseudorandom function; cuckoo hash

0 引言

在隱私集合交集（private set intersection，PSI）協(xié)議中，兩個(gè)互不信任的參與方P0和P1分別輸入自己的集合X0和X1，最終在不泄露任何額外信息的情況下讓參與方得到兩個(gè)集合的交集X0∩X1。在過(guò)去十年中，PSI協(xié)議在兩方惡意［1］、多方惡意［2］、云輔助模型［3］、小數(shù)據(jù)集模型［4］和抗量子領(lǐng)域［5］等方向的研究都取得了極大進(jìn)展，并在文獻(xiàn)［6］中進(jìn)行了詳細(xì)的總結(jié)。此外，PSI作為一種隱私保護(hù)技術(shù)在許多場(chǎng)景中得到了應(yīng)用，如多源異構(gòu)數(shù)據(jù)融合［7］、新冠接觸者行程［8］、廣告曝光度計(jì)算［9］和機(jī)器學(xué)習(xí)［10］等。

然而，在一些特殊場(chǎng)景下只有當(dāng)交集足夠大時(shí)，參與方才有得到交集的動(dòng)機(jī)。例如在隱私保護(hù)共享乘車(chē)應(yīng)用［11］中，只有當(dāng)乘客大部分行程相同時(shí)才會(huì)選擇拼車(chē)。所以門(mén)限隱私集合交集（threshold private set intersection，TPSI）協(xié)議是PSI問(wèn)題的一個(gè)特例，即當(dāng)且僅當(dāng)兩個(gè)參與者P0和P1的集合的交集基數(shù)|X0∩X1|達(dá)到門(mén)限值t時(shí)，參與方才能得到交集X0∩X1的信息，否則協(xié)議中止，參與方得不到關(guān)于交集的任何信息，如圖1和2所示。

Freedman等人［12］首次提出了TPSI協(xié)議的概念，并在半誠(chéng)實(shí)模型下設(shè)計(jì)了一個(gè)基于平衡哈希和同態(tài)加密的安全門(mén)限值測(cè)試協(xié)議，并基于此協(xié)議來(lái)實(shí)現(xiàn)了TPSI協(xié)議。Zhao等人［13］提出了一種基于秘密共享和半同態(tài)加密技術(shù)的門(mén)限秘密傳輸方案來(lái)實(shí)現(xiàn)兩方TPSI協(xié)議，但是該協(xié)議會(huì)泄露交集基數(shù)。Ghosh等人［14］提出了一種評(píng)估隨機(jī)線(xiàn)性函數(shù)的工具，并構(gòu)建了一個(gè)基于彈性秘密共享 （robust secret sharing，RSS）和代數(shù)技術(shù)的兩方TPSI協(xié)議。然而，代數(shù)技術(shù)需要大量的插值運(yùn)算，導(dǎo)致協(xié)議的通信開(kāi)銷(xiāo)較大。此外，RSS 解碼（即Reed-Solomon碼）算法的計(jì)算復(fù)雜度為O（n3），使得該協(xié)議無(wú)法在大集合上運(yùn)行。

Hallgren等人［11］在半誠(chéng)實(shí)模型下設(shè)計(jì)了一種兩方TPSI協(xié)議，并將其用于具有隱私保護(hù)的共享拼車(chē)應(yīng)用中，這使乘客能夠在不泄露旅行行程的情況下進(jìn)行拼車(chē)。但是該協(xié)議具有O（n3）的計(jì)算復(fù)雜度和O（n2）的通信復(fù)雜度。Zhao等人［15］基于加法同態(tài)加密和不經(jīng)意多項(xiàng)式計(jì)算在半誠(chéng)實(shí)模型下構(gòu)建了兩種兩方TPSI協(xié)議，分別在交集基數(shù)大于和小于門(mén)限值時(shí)輸出交集。Ghosh等人［16］研究了TPSI協(xié)議的通信復(fù)雜度，指出通信的下界為O（t），其中t為集差。此外，他們?cè)O(shè)計(jì)了一個(gè)基于加法同態(tài)加密的TPSI協(xié)議，將協(xié)議的通信復(fù)雜度降低到O（t2）。但是，當(dāng)集差t較大時(shí)，協(xié)議的通信復(fù)雜度較大，即O（t2）≈O（n2）。

Rindal等人［17］提出了一種基于向量不經(jīng)意線(xiàn)性評(píng)估（vector oblivious linear evolution，Vole）的不經(jīng)意偽隨機(jī)函數(shù)（oblivious pseudo-random function，OPRF） ，并用它實(shí)現(xiàn)了電路PSI協(xié)議，但該協(xié)議不能抵抗惡意敵手。Ghosh等人［18］設(shè)計(jì)了一個(gè)基于加性同態(tài)加密、不經(jīng)意傳輸和通用安全計(jì)算的擬線(xiàn)性復(fù)雜度的兩方TPSI協(xié)議，但是該協(xié)議處于理論階段并未具體實(shí)現(xiàn)。Raghuraman等人［19］提出了一種新的不經(jīng)意鍵值對(duì)存儲(chǔ)（obli-vious key-value stores，OKVS）的構(gòu)造方式，提高了OKVS方案的編解碼效率，并將其應(yīng)用在文獻(xiàn)［18］的電路PSI協(xié)議中，進(jìn)一步減少了協(xié)議的計(jì)算開(kāi)銷(xiāo)，但不能抵抗惡意敵手。

張恩等人［20］提出了一個(gè)基于彈性秘密共享的多方TPSI協(xié)議。協(xié)議分為輕量級(jí)協(xié)議和增強(qiáng)協(xié)議，分別可以抵抗不同程度的敵手合謀。但是該協(xié)議在秘密共享重構(gòu)階段同樣使用了RSS算法，在重構(gòu)階段的計(jì)算復(fù)雜度為O（n3），所以協(xié)議無(wú)法在大集合下運(yùn)行。此外，魏立斐等人［21］提出了一種雙云輔助的超閾值多方隱私集合交集（over-threshold multi-party private set intersection，OT-MP-PSI）協(xié)議，參與方共同計(jì)算至少屬于t個(gè)參與方集合交集的元素。該協(xié)議將計(jì)算復(fù)雜度較高的秘密分發(fā)和秘密重構(gòu)過(guò)程分別交給兩個(gè)不可信的云服務(wù)器來(lái)完成，可以解決參與者計(jì)算能力較弱和計(jì)算能力不平衡的問(wèn)題。但是該OT-MP-PSI協(xié)議在秘密重構(gòu)過(guò)程需要由服務(wù)器重遍歷整個(gè)有限域，所以協(xié)議的計(jì)算開(kāi)銷(xiāo)較大。Liu等人［22］首次提出了概率TPSI協(xié)議的概念，各參與方有與交集大小相關(guān)的概率獲得交集，并將Goldwasser-Sipser證明系統(tǒng)擴(kuò)展至多方設(shè)置，實(shí)現(xiàn)多方概率交集基數(shù)測(cè)試協(xié)議。該協(xié)議可以繞過(guò)計(jì)算交集基數(shù)的通信下界，極大地減少了協(xié)議的開(kāi)銷(xiāo)。

綜上，現(xiàn)存的TPSI協(xié)議均在半誠(chéng)實(shí)模型下實(shí)現(xiàn)，并且使用了同態(tài)加密、RSS和多項(xiàng)式插值等計(jì)算復(fù)雜度較高的算法。在用戶(hù)數(shù)據(jù)較大的場(chǎng)景下，采用以上算法的協(xié)議需要較長(zhǎng)的運(yùn)行時(shí)間，交集信息無(wú)法及時(shí)反饋給用戶(hù)。此外這些協(xié)議，無(wú)法抵抗惡意敵手的攻擊。本文提出了兩種TPSI協(xié)議，分別可以在半誠(chéng)實(shí)模型和惡意模型下運(yùn)行，并且兩個(gè)協(xié)議避免了計(jì)算成本較高的算法，僅需要使用對(duì)稱(chēng)密鑰算法和計(jì)算復(fù)雜度為O（n）的通用兩方安全計(jì)算。本文的主要貢獻(xiàn)如下：

a）在半誠(chéng)實(shí)模型下設(shè)計(jì)了一個(gè)高效的兩方TPSI協(xié)議，該協(xié)議基于哈希技術(shù)、OKVS和向量不經(jīng)意匹配測(cè)試（vector oblivious match test，VOMT）算法。通過(guò)哈希技術(shù)和OKVS減少了協(xié)議在安全門(mén)限值測(cè)試階段的計(jì)算復(fù)雜度。此外，使用VOMT算法提高了協(xié)議的計(jì)算效率，使協(xié)議在集合較大時(shí)仍可以高效運(yùn)行。

b）由于哈希技術(shù)無(wú)法在惡意模型下使用［23］，本文提出了向量不經(jīng)意解密匹配測(cè)試（vector oblivious decoding matching test，VODMT）算法，使用VODMT、OPRF和對(duì)稱(chēng)密鑰加密方案減少了協(xié)議在安全門(mén)限值測(cè)試階段的計(jì)算復(fù)雜度，從而構(gòu)造出了第一個(gè)可以在惡意模型下運(yùn)行的兩方TPSI協(xié)議。

c）分析并得出本文提出的兩個(gè)TPSI協(xié)議的計(jì)算復(fù)雜度和通信復(fù)雜度均為線(xiàn)性，并分別在惡意模型和半誠(chéng)實(shí)模型下證明了協(xié)議的安全性。

d）在不同大小集合下測(cè)試了協(xié)議的運(yùn)行時(shí)間。當(dāng)集合大小為220時(shí)，協(xié)議的在線(xiàn)運(yùn)行時(shí)間分別為226.20 s和409.76 s，是第一個(gè)可以在大集合（220）下運(yùn)行的TPSI協(xié)議，并通過(guò)實(shí)驗(yàn)對(duì)比得出本文的協(xié)議優(yōu)于先前的工作。

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

1.1 安全模型

安全模型包括半誠(chéng)實(shí)安全模型和惡意安全模型。在半誠(chéng)實(shí)安全模型下，敵手嚴(yán)格按照協(xié)議要求執(zhí)行，但是會(huì)試圖在交互過(guò)程中獲取額外信息。而在惡意模型下，敵手可以任意偏離協(xié)議，通過(guò)修改或省略消息等手段來(lái)獲取額外信息。本文中的協(xié)議均為兩方協(xié)議，在安全證明中只考慮其中一方腐敗的情形，且本文中對(duì)安全模型和腐敗參與方的定義遵循文獻(xiàn)［24，25］中的定義。

在半誠(chéng)實(shí)模型中，設(shè)π是理想兩方協(xié)議，用M表示任意參與方子集。在M中參與方在執(zhí)行輸入為（x，y）的協(xié)議π時(shí)，其視圖表示為viewπM（x，y，e）=（，rM1，…，rMt，m），其中e為安全參數(shù)，表示M中各個(gè)參與方的輸入，rM1，…，rMt表示在執(zhí)行過(guò)程中產(chǎn)生的隨機(jī)值，m表示在執(zhí)行協(xié)議過(guò)程中收到的消息。

定義1 令f為一個(gè)確定性函數(shù)。如果存在一個(gè)概率多項(xiàng)式時(shí)間算法S，滿(mǎn)足：

4 性能分析

在下文中分別使用協(xié)議A和B來(lái)表示本文2.1節(jié)和3.1節(jié)中所提出的協(xié)議。

4.1 計(jì)算復(fù)雜度分析

本節(jié)對(duì)協(xié)議的計(jì)算復(fù)雜度進(jìn)行分析。對(duì)于協(xié)議A，在哈希技術(shù)階段的計(jì)算復(fù)雜度與使用的哈希函數(shù)的數(shù)量有關(guān)，為O（kn）。在OKVS編碼和解碼算法階段的計(jì)算復(fù)雜度分別為O（εn+λ）和O（εn），在VOMT階段的計(jì)算復(fù)雜度為O（εn）。由此可見(jiàn)，協(xié)議A的計(jì)算復(fù)雜度為O（（ε+k）n）。對(duì)于協(xié)議B，在OPRF階段和OKVS編解階段協(xié)議的計(jì)算復(fù)雜度均為O（n），而在VODMT階段協(xié)議的計(jì)算復(fù)雜度為O（ln），l為在通用安全計(jì)算中對(duì)一個(gè)元素進(jìn)行解密匹配所使用與門(mén)的數(shù)量。因此，協(xié)議B的計(jì)算復(fù)雜度為O（ln）。

4.2 通信復(fù)雜度分析

本節(jié)對(duì)協(xié)議的通信復(fù)雜度進(jìn)行分析。對(duì)于協(xié)議A，在發(fā)送數(shù)據(jù)結(jié)構(gòu)D階段的通信復(fù)雜度為O（εnλ），在進(jìn)行VOMT階段的通信復(fù)雜度為O（εnλ）。所以協(xié)議A的通信復(fù)雜度為O（εnλ）。對(duì)于協(xié)議B，在OPRF階段和發(fā)送數(shù)據(jù)結(jié)構(gòu)D階段的通信復(fù)雜度均為O（n），在VODMT階段的通信復(fù)雜度為O（（κ+l）n）。所以協(xié)議B的通信復(fù)雜度為O（（κ+l）n）。

4.3 復(fù)雜度對(duì)比

本節(jié)分別對(duì)比了本文協(xié)議與之前工作的計(jì)算復(fù)雜度與通信復(fù)雜度，如表1所示。

4.4 實(shí)驗(yàn)和對(duì)比

本文的協(xié)議使用Java和部分C++實(shí)現(xiàn)，VOMT功能使用ABY協(xié)議實(shí)現(xiàn)。VODMT功能使用SPDZ協(xié)議（https：//github.com/data61/MP-SPDZ）和mpc4j庫(kù)（https：//github.com/ali-baba-edu/mpc4j）實(shí)現(xiàn)。本文使用的OKVS方案和OPRF方案通過(guò)文獻(xiàn)［20］中的代碼實(shí)現(xiàn)。實(shí)驗(yàn)中的其他參數(shù)及取值如表2所示，其中n表示集合大小。

本文把協(xié)議分為偽隨機(jī)值分發(fā)階段和門(mén)限值測(cè)試階段，并分別在{216，217，…，220}集合大小下測(cè)試了協(xié)議的運(yùn)行時(shí)間，并給出了協(xié)議在線(xiàn)運(yùn)行的總時(shí)間，實(shí)驗(yàn)結(jié)果如表3和4所示。結(jié)果表明，本文提出的兩個(gè)協(xié)議在集合大小為220時(shí)運(yùn)行時(shí)間分別為226.20 s和409.76 s，是第一個(gè)可以在220大小集合下運(yùn)行的TPSI協(xié)議。

本文與現(xiàn)存的TPSI協(xié)議在不同集合大小下對(duì)比了協(xié)議的nzCbdxYKkLqWAN4V2tkNSA==運(yùn)行時(shí)間，由于暫時(shí)無(wú)法找到可以抵抗惡意敵手的TPSI協(xié)議，所以本文與目前可實(shí)現(xiàn)的半誠(chéng)實(shí)兩方TPSI協(xié)議進(jìn)行對(duì)比，對(duì)比結(jié)果如表5所示。

根據(jù)表5可以看出，協(xié)議A和B在211大小的集合下的運(yùn)行時(shí)間分別為0.77 s和1.07 s，而文獻(xiàn)［11，13］的協(xié)議則需要728.10 s和778.96 s，所以本文協(xié)議在運(yùn)行效率上相較于以往工作有較大提升。

電路PSI協(xié)議理論上可以在交集上實(shí)現(xiàn)任何功能，但現(xiàn)存的電路PSI協(xié)議暫未實(shí)現(xiàn)門(mén)限值測(cè)試功能，所以本文在與電路PSI協(xié)議對(duì)比時(shí)減去了門(mén)限值測(cè)試階段所消耗的時(shí)間（即標(biāo)準(zhǔn)兩方PSI協(xié)議），對(duì)比結(jié)果如表6所示。

從表6中可以看出，協(xié)議A和B相較于文獻(xiàn)［29］在運(yùn)行時(shí)間上均有較大提升。協(xié)議A相較于文獻(xiàn)［19］在運(yùn)行時(shí)間上提升了約10%，而協(xié)議B在集合大小小于215時(shí)協(xié)議的運(yùn)行時(shí)間優(yōu)于文獻(xiàn)［19］，并且文獻(xiàn)［19，29］均無(wú)法抵抗惡意敵手，所以本文協(xié)議在不同的模型下都具有較好的實(shí)用性。

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

本文提出了可以抵抗半誠(chéng)實(shí)敵手和惡意敵手的兩方TPSI協(xié)議，根據(jù)實(shí)驗(yàn)數(shù)據(jù)表明本文的協(xié)議可以在大數(shù)據(jù)集下高效運(yùn)行，具有較好的實(shí)用價(jià)值。此外，可以從實(shí)驗(yàn)中得出，雖然協(xié)議效率有一定提升，但是安全門(mén)限值測(cè)試階段仍然占協(xié)議開(kāi)銷(xiāo)的較大部分，因此之后將研究設(shè)計(jì)一個(gè)更高效的安全門(mén)限值測(cè)試協(xié)議和實(shí)現(xiàn)多方惡意門(mén)限隱私集合交集協(xié)議。

參考文獻(xiàn)：

［1］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. Cham： Springer， 2020： 739-767.

［2］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.

［3］張靜， 田賀， 熊坤， 等. 基于云服務(wù)器的公平多方隱私集合交集協(xié)議［J］. 計(jì)算機(jī)應(yīng)用， 2023，43（9）：2806-2811. （Zhang Jing， Tian He， Xiong Kun， et al. Fair multi-party private set intersection protocol based on cloud server［J］. Journal of Computer Applications， 2023，43（9）：2806-2811.）

［4］張蕾， 賀崇德， 魏立斐. 高效且惡意安全的三方小集合隱私交集計(jì)算協(xié)議［J］. 計(jì)算機(jī)研究與發(fā)展， 2022， 59（10）： 2286-2298. （Zhang Lei， He Chongde， Wei Lifei. Efficient and malicious secure three-party private intersection computation protocol for small set［J］. Computer Research and Development， 2022， 59（10）： 2286-2298.）

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

［6］魏立斐， 劉紀(jì)海， 張蕾. 面向隱私保護(hù)的集合交集計(jì)算綜述［J］. 計(jì)算機(jī)研究與發(fā)展， 2022， 59（8）： 1782-1799. （Wei Lifei， Liu Jihai， Zhang Lei. Survey of privacy preserving oriented set intersection computation［J］. Computer Research and Development， 2022， 59（8）： 1782-1799.）

［7］丁江， 張國(guó)艷， 魏子重，等. 面向多源異構(gòu)數(shù)據(jù)融合的隱私集合求交研究［J］. 信息網(wǎng)絡(luò)安全， 2023， 23（8）： 86-98. （Ding Jiang， Zhang Guoyan， Wei Zichong， et al. Multi-source heteroge-neous data collaboration via private set intersection［J］. Netinfo Secu-rity， 2023， 23（08）： 86-98.）

［8］Duong T， Phan D H， Trieu N. Catalic： delegated PSI cardinality with applications to contact tracing［C］//Proc of the 26th Internatio-nal Conference on Theory and Application of Cryptology and Information Security. Cham：Springer， 2020： 870-899.

［9］Lyu Siyi， Ye Jinhui， Yin Sijie， et al. Unbalanced private set intersection cardinality protocol with low communication cost［J］. Future Generation Computer Systems， 2020， 102： 1054-1061.

［10］Mohassel P， Zhang Yupeng. SecureML： a system for scalable privacy-preserving machine learning［C］//Proc of IEEE Symposium on Secu-rity and Privacy. Piscataway，NJ：IEEE Press， 2017： 19-38.

［11］Hallgren P， Orlandi C， Sabelfeld A. PrivatePool： privacy-preserving ridesharing［C］//Proc of the 30th IEEE Computer Security Foundations Symposium. Piscataway，NJ：IEEE Press， 2017： 276-291.

［12］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.

［13］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.

［14］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. Cham： Sprin-ger， 2019： 154-185.

［15］Zhao Yongjun， Chow S S M. Can you find the one for me？［C］//Proc of Workshop on Privacy in Electronic Society. New York： ACM Press，2018： 54-65.

［16］Ghosh S， Simkin M. The communication complexity of threshold private set intersection［C］//Proc of Annual International Cryptology Conference. Cham： Sprin-ger， 2019： 3-29.

［17］Rindal P， Schoppmann P. VOLE-PSI： fast OPRF and circuit-PSI from vector-OLE［C］//Proc of Annual International Conference on Theory and Applications of Cryptographic Techniques. Cham： Springer International Publishing， 2021： 901-930.

［18］Ghosh S， Simkin M. Threshold private set intersection with better communication complexity［C］//Proc of International Conference on Public-Key Cryptography. Cham： Springer， 2023： 251-272.

［19］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.

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

［21］魏立斐， 劉紀(jì)海， 張蕾， 等. 雙云輔助的超閾值多方隱私集合交集計(jì)算協(xié)議［J］. 軟件學(xué)報(bào)， 2023，34（11）：5442-5456. （Wei Lifei， Liu Jihai， Zhang Lei， et al. Two cloud-assisted over-threshold multi-party private set intersection calculation protocol［J］. Journal of Software， 2023，34（11）：5442-5456.）

［22］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.

［23］Rindal P， Rosulek M. Malicious-secure private set intersection via dual execution［C］//Proc of ACM SIGSAC Conference on Computer and Communications Security. New York：ACM Press， 2017： 1229-1242.

［24］Lindell Y. How to simulate it—a tutorial on the simulation proof technique［M］//Tutorials on the Foundations of Cryptography： Dedicated to Oded Goldreich. 2017： 277-346.

［25］Rindal P， Rosulek M. Improved private set intersection against malicious adversaries［C］//Proc of Annual International Conference on Theory and Applications of Cryptographic Techniques. Cham： Sprin-ger International Publishing， 2017： 235-259.

［26］Gonnet G H. Expected length of the longest probe sequence in hash code searching［J］. Journal of the ACM， 1981， 28（2）： 289-304.

［27］Pagh R， Rodler F F. Cuckoo hashing［J］. Journal of Algorithms， 2004， 51（2）： 122-144.

［28］Pinkas B， Schneider T， Zohner M. Scalable private set intersection based on OT extension［J］. ACM Trans on Privacy and Security， 2018， 21（2）： 1-35.

［29］Pinkas B， Schneider T， Tkachenko O， et al. Efficient circuit-based PSI with linear communication［C］//Proc of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham：Springer， 2019： 122-153.

收稿日期：2023-12-11；修回日期：2024-01-26 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（62072159，62002103，6207608）；河南省科技攻關(guān)項(xiàng)目（232102211057）

作者簡(jiǎn)介：賈正坤（1999—），男，河南新鄉(xiāng)人，碩士研究生，主要研究方向?yàn)榘踩喾接?jì)算；張恩（1974—），男（通信作者），河南新鄉(xiāng)人，教授，碩導(dǎo)，博士，主要研究方向?yàn)榘踩喾接?jì)算（zhangenzdrj@163.com）；王夢(mèng)濤，男，河南周口人，碩士研究生，主要研究方向?yàn)榘踩喾接?jì)算．