多方隱私集合交集及秘密信譽值比較協(xié)議

中圖分類號：TP309 文獻標志碼：A 文章編號：1000-2367（2025）05-0121-10

隱私集合交集（private set intersection，PSI）允許兩個或多個參與方秘密地計算交集而不泄露交集以外的其他信息，為用戶提供服務(wù)的同時最大程度地保護隱私[1].以銀行征信查詢?yōu)槔恒y行借貸業(yè)務(wù)需查詢用戶在本地和其他銀行的信譽狀況，判斷用戶是否信譽良好且具有還貸能力，從而降低信貸風(fēng)險.在這個過程中用戶在不同機構(gòu)的數(shù)據(jù)作為隱私信息無法在多家銀行直接共享[2」，而現(xiàn)實中又需要對借貸用戶進行信譽評估.因此，在保護各方隱私的前提下，安全查詢借貸用戶在其他銀行中的信譽狀況是一個值得研究的問題.

兩個參與方場景下的PSI（簡稱兩方PSI）大多基于不經(jīng)意傳輸或公鑰加密等技術(shù)手段實現(xiàn)，已有多種高效且安全的實現(xiàn)方案.隨著PSI應(yīng)用場景的不斷擴大，研究愈發(fā)深人，PSI協(xié)議也從兩方擴展到多方.而多方隱私集合交集（multiparty private set intersection，MPSI）致力于在不泄露任何參與方信息的前提下，計算多個參與方數(shù)據(jù)集的交集.當兩方PSI擴展到多方時，隨著參與方的數(shù)量增多，使用同態(tài)方案造成的計算負荷不可忽視，且各參與方數(shù)據(jù)集規(guī)模差異大，導(dǎo)致隱私保護難度加大，易出現(xiàn)隱私泄露.

針對兩方PSI協(xié)議擴展到多方時存在交集計算易失敗以及用戶在多個機構(gòu)中的查詢結(jié)果不一致、無法準確評估信譽等問題，本研究利用EIGamal算法和多密鑰加解密，提出多方用戶交集和用戶交集基數(shù)的秘密信譽值比較協(xié)議.該協(xié)議在保護查詢方和被查詢方隱私的同時，通過布隆過濾器（bloom filter，BF）和 El-Gamal加密計算交集用戶并完成秘密信譽值比較.此外，考慮到實際應(yīng)用中用戶在所有機構(gòu)中均創(chuàng)建賬戶的概率較低，提出隱私集合多方交集基數(shù)的概念和求解方法，利用信譽過濾器值和多密鑰加解密構(gòu)建更為實用的信譽評估方案.最后證明了協(xié)議在半誠實模型下的安全，在不同數(shù)量級集合輸人的情況下分別測試2種協(xié)議各階段的在線計算時間和查詢方解密時間，與其他多方隱私集合計算協(xié)議進行了對比.

1相關(guān)工作

多方隱私集合交集是兩方PSI向兩個以上參與方的自然延伸，研究最初，并未像兩方PSI那樣受關(guān)注，隨著應(yīng)用需求的擴展，MPSI已經(jīng)成為了新的研究熱點.FREEDMAN等[3]提出基于同態(tài)加密和多項式的MPSI協(xié)議，將集合元素表示為多項式的根，為多方協(xié)議構(gòu)造提供了思路.之后，KISSNER等[4使用加性同態(tài)加密和私鑰秘密共享實現(xiàn)的MPSI協(xié)議計算和通信開銷是集合大小和參與者數(shù)量的兩倍，無法滿足實際應(yīng)用要求.此后降低同態(tài)密碼技術(shù)的MPSI協(xié)議的計算開銷和通信開銷已成為一個重要的目標.2022年，BAY等[5將文獻[6]兩方PSI拓展到多方，但協(xié)議運行時間較長、效率不高.RUAN等[提出基于BF 和Shamir 閾值秘密共享方案的MPSI協(xié)議，雖在效率上有所提高，但交互輪數(shù)多.在現(xiàn)有的MPSI研究中，通信成本和協(xié)議輪數(shù)是影響性能的主要因素，隨著參與方數(shù)量增多，導(dǎo)致協(xié)議產(chǎn)生高昂的計算和通信開銷，影響其在現(xiàn)實場景的可行性，

秘密數(shù)據(jù)比較本質(zhì)是在不泄露參與方輸入信息的情況下比較出兩數(shù)值大小， YAO^[8] 最早提出的“百萬富翁問題\"形象描述了此問題.匿名投票作為秘密數(shù)據(jù)比較協(xié)議的應(yīng)用場景之一，借助密碼學(xué)技術(shù)剝離對可信第三方的依賴.2021年張靜等[9提出一種采用0—1編碼的數(shù)據(jù)比較協(xié)議，通過改進保密數(shù)據(jù)編碼規(guī)則和EIGamal同態(tài)加密解決安全兩方計算問題，保證協(xié)議半誠實安全但需要3輪通信.2022年李順東等[10提出結(jié)合ElGamal乘法同態(tài)性質(zhì)和保密洗牌的零知識證明設(shè)計了抵抗惡意安全的保密比較協(xié)議，協(xié)議中對m個數(shù)據(jù)的加密，需要 24m+4 次模冪運算，計算復(fù)雜度與數(shù)據(jù)范圍成正比且在大數(shù)比較時效率較低.

2 預(yù)備知識

2.1 布隆過濾器

布隆過濾器（BF）[11]是一個擁有 k 個哈希函數(shù) {h₁，h₂，…，h_k} 長度為 Ψ_m 的比特數(shù)組， BF={BF[1] BF[2]，…，BF[m]} .當插入數(shù)據(jù)集 X={x₁，…，x_n} 的元素 x_i 到 BF中時，將元素 x_i 使用 k 個哈希函數(shù)映射到 {h₁（x_i），…，h_k（x_i）} 的位置設(shè)置為1，如附錄圖S1所示.

BF中的相應(yīng)位置均被設(shè)置為1，即 BF[h_u（y）]=1. 此時，假陽性發(fā)生的概率與布隆過濾器長度 Ψ_m 、哈希函數(shù)個數(shù) k 和元素 n 直接相關(guān)[2]，其概率為 ，且該概率上界關(guān)于 k 的可忽略值為 ε=ρ^k?（1+ 0k lnm-kln）），當?可忽略不計時，對上式進行約束后k，m分別取值k= 愛和機

2.2 混淆布隆過濾器

DONG 等[12]提出混淆布隆過濾器（garbled bloom filter，GBF）的概念：哈希函數(shù)映射位置不再存放單個比特，而是 λ 比特的字符串.比如當插人元素 x_ι 到GBF中時，哈希函數(shù)映射位置不再是1，而是一個隨機數(shù)，且映射到所有位置的值異或后的結(jié)果為 x_ι ，即 ，其余空位置填充隨機值.當插入 x_ι （204號元素到GBF時構(gòu)造如附錄圖S2所示.

GBF插人第 n 個元素到某一映射位置被占據(jù)的概率為 ，而所有 k 個位置被占據(jù)的概 In m－2klnP）），此時 GBF創(chuàng)建失敗.

2.3 ElGamal加密算法

ElGamal[13]是一種滿足乘法同態(tài)的公鑰加密算法，其安全性基于離散對數(shù)困難問題，它包含了一個生成元 g 、模素數(shù) p 、私鑰 α 和公鑰 h .ElGamal算法可分為3個主要部分：密鑰生成KenGen、加密 Enc 和解密 Dec ：KenGen：產(chǎn)生一個大素數(shù) p 和一個循環(huán)群 Z_ρP^? （20 ，g（gρP^? 的生成元.隨機選取一個私鑰（20號 α∈Z_ρ^? ，計算 h=g^α mod p 作為公鑰.

Enc ：設(shè)明文消息 M∈Z_ρ^* ，隨機選擇 r∈Z_?P^?* ， 2≤r≤p-2 ，則加密密文 Enc（M）=（c₁，c₂）=（g^r mod

Dec：對密文 Enc（M）=（c₁，c₂） ，則解密明文 M=Dec（c₁，c₂）=c₂（c₁^α）^-1 mod p

ElGamal具有乘法同態(tài)性質(zhì)： Enc（m₁?m₂）=Enc（m₁）?Enc（m₂） ：

同時滿足標量乘法運算： c?Enc（M）=Enc（c?M）

3協(xié)議設(shè)計

針對銀行跨機構(gòu)安全查詢用戶信譽問題，設(shè)計2種多方交集及秘密信譽值比較協(xié)議，查詢方獲得用戶在不同機構(gòu)中的信譽比較結(jié)果，協(xié)議功能如附錄圖 S3所示.協(xié)議涉及的角色分別為：持有集合 X={（x₁，v₁） （204號 …，（x_?mR，v_?mR）} 的查詢方 R，x_i 和 v_i 分別表示用戶的身份信息和信譽值 .n 個被查詢方 S₁，…，S_n 分別持有大小為 m₁，…，m_n 的集合 個哈希函數(shù)（204號 h_?1，…，h_?k ： 是抗碰撞哈希函數(shù)， κ 表示其輸出長度，對任意輸人 x∈{0，1}^* 使用哈希函數(shù)計算后獲得結(jié)果 h_n（x）∈{0，1}^κ ：

3.1 構(gòu)造VBF

在整個交互中，被查詢方利用混淆布隆過濾器構(gòu)造隱藏輸入集.對元素 x 使用 k 個哈希函數(shù)映射的位置將填充信譽值的隨機份額，其余空位置不再填充隨機值而是“1\"值，該結(jié)構(gòu)稱為信譽過濾器（value bloom fil-ter，VBF）.這樣構(gòu)造的VBF 既滿足 v=?_u=1^kVBF_i[h_u（x_l）] ，又適用于ElGamal乘法同態(tài)，避免了對“0\"的加密.當 n 個被查詢方 S₁，…，S_n 對用戶集合 Y₁，…，Y_n 構(gòu)造 VBF_i 時，具體算法如下.

算法1 VBFO）

輸入：集合 12. end if

輸出：構(gòu)造 VBF_i ： 13. else

1.VBF=NULL 14. lastShare←lastShareVBF[index] 2.for j=1 to m_i do 15. endif

3. value=v_jⁱ （20 16. end for

4. for u=1 to k do 17. （20 5. index=h_?（y_jⁱ） （20 18. end for

6. if VBF[index]==NULL then 19. for j=1 to m do

7. if emptyBin==-1 then 20. if VBF[i]=NULL then

8. emptyBin=index 21. VBF[j]←1

9. else 22. end if

10. VBF[index]{0，1}^κ 23. end for

11. lastShare $$ lastShareVBF[index] 24. return VBF;

3.2 多方隱私集合交集

多方交集秘密信譽值比較協(xié)議利用BF和VBF隱藏被查詢方的用戶信息，并由被查詢方將操作轉(zhuǎn)移到離線階段以提升協(xié)議計算效率.VBF經(jīng)對應(yīng)映射位置異或可獲得信譽值，而 BF需將映射后的值經(jīng)ElGamal加密發(fā)給查詢方 R .考慮EIGamal算法無法對“O\"值進行加密，被查詢方 S_i 要在位數(shù)組 BF 未設(shè)置為1處填充隨機數(shù) r 后加密.當查詢方 R 用ElGamal公鑰對 n 個被查詢方 S_i 發(fā)來的 BF_i 進行運算時，由于乘法同態(tài)性，相同映射為“1\"的位置經(jīng)密文下乘法運算后保留明文上的“1\"值， R 計算后獲得隱藏交集用戶身份信息的BF

在協(xié)議1中，查詢方 R 生成并公開密鑰對 （?_??，sk） .隨后 n 個被查詢方 S₁，…，S_n 對用戶信息中的 {y_i} 生成 BF_i 后，利用 Π_pk 加密獲得 EBF_i=Enc（BF_i） ）并發(fā)送給查詢方 R.R 計算 后將該結(jié)果乘以信譽閾值密文返回被查詢各方， EBF 中隱藏交集用戶信息.查詢方 R 可通過私鑰解密得到包含所有交集用戶的 BF ，經(jīng)設(shè)置的信譽閾值密文計算 w=EBF?Enc（v^-1） 后返回各方.最后被查詢方 S_i 利用離線階段生成的 VBF_i 與密文 w 進行標量乘并發(fā)送，查詢方 R 獲得 n 方交集用戶的信譽值比較結(jié)果.協(xié)議1具體執(zhí)行步驟如下.

協(xié)議1多方交集秘密信譽值比較協(xié)議

輸入：查詢方 R 的數(shù)據(jù)集 X ，被查詢方 S₁，…，S_n 的數(shù)據(jù)集 Y₁，…，Y_n，i∈[1，n]，R 和 S_i 的集合大小分別為 m_R，m₁，…，m_n，j∈[1，m_i] .輸出：交集用戶 {w} ，秘密信譽值比較結(jié)果 ∣V∣ ：

步驟1 初始化

（1）查詢方 R 生成ElGamal密鑰對 （pk，sk）←KenGen ，并隨機選擇 k 個哈希函數(shù) h₁，…，h_k，u∈[1 ^k] ，將 （ρk，h₁，…，k_k） 公開.

步驟2 預(yù)處理階段

（1）查詢方 R 對待查詢用戶 X={（x_ι，v_ι）}，ι∈[1，m_R] ，計算信譽閾值密文 Enc（v^-1） ;

（2）被查詢方對持有集合 中用戶身份信息構(gòu)造 VBF_i 和 BF_i .對 S_i 中每個用戶的身份信息 y_jⁱ 和信譽值 v_jⁱ 生成 VBF_i ，使得 VBF_i 中相應(yīng)哈希映射位置異或結(jié)果滿足 .對用戶身份信息 {y₁ⁱ，…，y_miⁱ} 構(gòu)造 BF_i 使用公鑰 Δ_Pk 加密獲得 EBF_i=Enc（BF_i） ，各方將生成的 EBF_i 發(fā)送給任意一個 ：

（3） S_j 將對集合生成的 EBF_j 計算 EBF_i?EBF_j 發(fā)送給查詢方 R ·步驟3在線階段.查詢方 R 接收到 EBF=（EBF₁，…，EBF_n） ，準備計算

（1）查詢方 R 計算 ，并將結(jié)果 value=EBF?Enc（v^-1） 返回給 n 個被查詢方S₁，…，S_n

（2）被查詢方 S_i 收到消息value后，計算 w_i=value?VBF_i ，并發(fā)送給查詢方 R ：

步驟4 離線階段

（1）查詢方 R 收到 后，對用戶 x_i 使用 k 個哈希函數(shù) h₁，…，h_k 計算 h_u（x） 獲得 w_i[h_u（x_l）] 若用戶 x_ι 是查詢方 R 同 n 個被查詢方的交集用戶，則獲得秘密信譽值 可從解密結(jié)果 判斷信譽狀況，若 ，說明該交集用戶在其中一家機構(gòu)信譽不良，記∣V∣=∣{x_ι}?V ，最后輸出 ∣V∣

正確性分析查詢方 R 獲得 n 個被查詢方的 BF_i 經(jīng)ElGamal公鑰 Π_pk 加密的結(jié)果 EBF_i=Enc（BF_i） 計算獲得 .當查詢的用戶 x_ι 是交集用戶時，由于 ElGamal 的乘法同態(tài)性 EBF 中交集元素對應(yīng)位置保持\"1”值， R 輸入信譽閾值 Enc（v^-1） 計算后返回.推導(dǎo)如下：

被查詢方 S_i 對查詢方 R 提供的信譽閾值 Enc（v^-1） 輸入信譽值明文進行計算，利用ElGamal標量乘法性質(zhì)即可獲得交集用戶的秘密信譽值比較結(jié)果：

因此，當查詢 x_ι 是交集用戶時，協(xié)議1可正確輸出其在所有機構(gòu)不良信譽.

3.3 多方隱私集合交集基數(shù)

協(xié)議1計算了查詢方 R 同 n 個被查詢方的交集用戶，但當待查詢用戶未在所有機構(gòu)創(chuàng)建賬戶，或僅部分銀行留有該用戶信譽信息時，查詢方 R 執(zhí)行協(xié)議1無法找到用戶在其他機構(gòu)的信譽，導(dǎo)致比較失敗，從而無法準確評估信譽.現(xiàn)實中用戶在 n 個機構(gòu)均創(chuàng)建賬戶的概率較低，更多的是在部分機構(gòu)設(shè)有賬戶和信譽信息，此時只需評估用戶在這些機構(gòu)中的信譽情況即可.傳統(tǒng)的交集基數(shù)是指所有方都出現(xiàn)的交集元素個數(shù)，例如文獻[14]所求交集基數(shù).而本場景需確定用戶在多少個機構(gòu)中存在，現(xiàn)有交集基數(shù)求解方法無法滿足.

因此本節(jié)設(shè)計了多方交集基數(shù)及秘密信譽值比較協(xié)議，使查詢方獲得待查詢用戶在 n 家機構(gòu)中出現(xiàn)的基數(shù)1≈1 和不良信譽次數(shù) ∣V∣ ：

在協(xié)議2中， n 個被查詢方 S₁，…，S_n 分別生成密鑰對 （?_Pk_i，sk_i） ，并將公鑰 ?_Pk_i 發(fā)送給查詢方 R ，由 R 計算公共公鑰 ，在之后的執(zhí)行步驟中用此公鑰加密參數(shù).被查詢方 S_i 對輸入元素 {（y_jⁱ，v_jⁱ）} 生成 VBF_i 并加密.對新用戶來說，若在本機構(gòu)中沒有信譽記錄，則設(shè)定信譽值為安全臨界值.當查詢方 R 對集合 {（x_l，v_l）} 中元素 x_ι 映射到 VBF_i 相應(yīng)位置獲得份額 VBF_i[h_u（x_l）] ，只有輸入 x_ι 也是被查詢方 S_i 的用戶時，才能通過異或份額計算出正確的秘密信譽值份額 ，但無法解密.查詢方 R 查詢用戶 x_ι 在 n 家機構(gòu)的情況，獲得 n 個密文結(jié)果 c_ι，1，…，c_ι，n ，并對用戶的信譽值 v_l 計算 Enc（v_ι^-1） ，利用ElGamal算法乘同態(tài)特性計算 c_ι，i?Enc（v_ι^-1） ，并將結(jié)果發(fā)送給 n 個被查詢方 S_i .由 S_i 使用私鑰 Δ_ski 提供解密份額后返回，查詢方 R 完成聚合解密后獲得交集基數(shù) ∣w∣ 和信譽不良個數(shù) ∣V |.協(xié)議2具體執(zhí)行步驟如下.

協(xié)議2多方交集基數(shù)及秘密信譽比較協(xié)議

輸入：查詢方 R 的數(shù)據(jù)集 X ，被查詢方 S_i 的數(shù)據(jù)集 Y_i，i∈[1，n] ，集合大小為分別為 m_?R，m_?1，…，m_n （204號 j∈[1，m_i]

輸出：交集基數(shù) 1≈1 ，信譽不良基數(shù)

步驟1 初始化

（1）被查詢方 S_i 生成ElGamal密鑰對 （?_pk_i，sk_i） ，將公鑰 ?_Pk_i 發(fā)送給查詢方 R，i∈[1，n] （2）查詢方 R 計算 并選擇 k 個哈希函數(shù)，公開參數(shù) （ρk，h₁，…，h_k） ：

步驟2 預(yù)處理階段

（1）查詢方 R 對每個用戶 x_i 相應(yīng)的信譽值 v_ι ，使用公鑰 _pk 計算 Enc（v_l^-1），l∈[1，m_R]

（2）被查詢方 S_i 對自己的集合 ，生成哈希映射后的 VBF_i ，并使用公鑰 Π_pk 加密發(fā)送給查詢方 R .這樣被查詢方 S_i 生成的 VBF_i 整體由密文構(gòu)成，元素映射后異或結(jié)果為 Enc（v_jⁱ） ，其余位置為密文 Enc（1） ·

步驟3在線階段.查詢方 R 接收到 VBF_i=（VBF₁，…，VBF_n） ，準備計算：

（1）查詢方 R 對元素 X={（x_ι，v_ι）} 使用 k 個哈希函數(shù)計算 c_ι，i^u=VBF_i（h_u（x_ι）） 對 k 個 c_l，i^u 聯(lián)合計算（204號 ，其中 i∈[1，n]，l∈[1，m_R]，u∈[1，k].

（2）對查詢方 R 在預(yù)處理階段計算的信譽值密文 Enc（v_l^-1） ，計算 C_ι，i=c_ι，i?Enc（v_ι^-1） ，并將 （C_ι，1，…， C_ι，n ）發(fā)送給每一個被查詢方 S₁，…，S_n ：

（3）被查詢方 S_i 使用各自持有的私鑰 sk_i ，對 （C_ι，1，…，C_ι，n） 計算解密份額 mod p ， ，將 share_l，i 發(fā)送給查詢方.

步驟4 離線階段

（1）查詢方 R 收到 n 方發(fā)送的密文份額后 （share_ι，1，…，share_ι，n） 后，計算 modp ，解密計算獲得明文 Dec（Cipher_ι，i），i∈[1，n]，ι∈[1，m_R]

（2）若成功解密 w_l，i=Dec（Ci?her_l，i） ，則有 ∣τw∣=∣{x_l}?w∣ ，說明用戶在其中一家機構(gòu)中存在賬戶.查詢方R 繼續(xù)計算Cipher，;，從解密結(jié)果ω 判斷信譽狀況，若 w_l，ilt;1 ，則有 ∣V∣=∣{x_ι}∪V∣ ，說明用戶在一家機構(gòu)中信譽狀況不佳.最終輸出

正確性分析 n 個被查詢方 S₁，…，S_n 對集合 Y_i 生成的 VBF_i 使用公鑰 Π_pk 加密后隱藏信譽值明文.查詢方 R 在獲得 S_i 發(fā)送的 VBF_i 后，計算待查詢用戶 x_ι 在各方 VBF_i 中映射到的值 c_l，i^u=（c_l，i¹，…，c_l，i^k）= ，異或后結(jié)果為 .對 i∈[1，n] ，查詢方對 c_lⁱ 與用戶 x_ι 對應(yīng)秘密信譽值進行運算并返回 C_l，i=c_l，i?Enc（v_l^-1）=（c_l，1?Enc（v_l^-1），…，c_l，n （20 Enc（v_ι^-1） ）.被查詢方 S_i 提供解密份額 mod mod p ），查詢方 R 計算 ：

當查詢方 R 最終解密 mod p 時：

3.4 多密鑰解密

在3.3節(jié)中協(xié)議2要求公鑰由 n 個被查詢方 S₁，…，S_n 的公鑰 ?_Pk_i 聚合而成，所有參數(shù)基于該公鑰加密，其中 S_i 保留私鑰.查詢方 R 只有獲得足夠多的私鑰份額，才能成功解密輸出消息 或 ⊥ .若查詢方 R 有交集用戶 {（x_l，v_l）} ，被查詢方 S_i 在 VBF_i 中輸入對應(yīng)用戶可獲得 Enc（v_i） .利用ElGamal算法的乘法同態(tài)性實現(xiàn)，就能實現(xiàn) v_i 和 v_ι 的大小比較 （v_igt;v_i 或 v_ι≤v_ι ），具體協(xié)議描述如下.

協(xié)議3秘密信譽值比較協(xié)議

輸入：查詢方 R 的秘密信譽值 v_ι ，被查詢方 S_i 的秘密信譽值 v_i 輸出： v_ι 和 v_i 秘密信譽值比較結(jié)果.

步驟1被查詢方 s 生成ElGamal加密公鑰對 （?_Pk_i，sk_i） ，將公鑰 ?_Pk_i 發(fā)送給查詢方 R，R 計算公鑰 ，公開 Δ_Pk ，任一被查詢方 S_i 持有私鑰 sk_i=α ：

步驟2查詢方 R 查詢用戶 x_ι 在被查詢方 S_i 的 VBF_i 中對應(yīng)秘密信譽值 Enc（v_i）

步驟3查詢方 R 使用公鑰 Δ_Pk 加密 v_l^-1 得到 mod p， mod p ），計算（c₁^′，c₂^′）=Enc（v_l^-1）?Enc（v_i） 并結(jié)果發(fā)送給被查詢方 S_i ：

步驟 4被查詢方 S_i 收到 （c₁^'，c₂^'） 后，使用私鑰 解密計算 并發(fā)給查詢方 R 步驟5查詢方 R 將收到的 n 個 C_ι，i 聯(lián)合計算 ，輸出 （2

正確性分析參與解密的被查詢方 S_i 各自持有ElGamal密鑰對 （Δ_?ki，sk_i） ，由查詢方 R 計算總公鑰 ，又 mod ? ，則公鑰 Π_pk 滿足

當被查詢方 S_i 對明文消息 M 選擇隨機數(shù) 進行加密時，則有：

查詢方 R 解密時計算 mod p ，但總私鑰 sk 未知，需要 S_i 返回后 mod Σ_P 聯(lián)合計算 解密，結(jié)果如下：

M 對應(yīng) ，根據(jù)解密出 M 與\"1”的大小關(guān)系，判定用戶在被查詢方 S_i 的信譽值狀況，可確定查詢的用戶在被查詢方 S_i 中存在交集.若 Mlt;1 則說明用戶在被查詢方 S_i 中信譽不良.

4安全性證明

采用被廣泛接受的模擬范式[15]來證明協(xié)議1、2、3的安全性.

定理1協(xié)議1在半誠實模型下安全地計算多方集合交集及信譽狀況.

證明假設(shè)存在多項式時間模擬器 Sim_R 和模擬器 Sim_s ，使得 Sim_R 和 View_R^π 以及 Sim_s 和 View_s^π 在計算上無法區(qū)分，即：

Sim_s{Y_i，⊥}≡View_s^π.

當式（7）、（8）成立時多方交集計算協(xié)議 π 在半誠實敵手存在時是安全的，

首先，假設(shè)查詢方 R 是腐敗方的情況，構(gòu)造模擬器 Sim_R 模擬 R 的視圖.模擬器 Sim_R 收到 R 的集合輸入X 和輸出結(jié)果 1V |，腐敗方 R 執(zhí)行協(xié)議時的真實視圖為 View_R^π ，即 View_R^π={X，（ph，sk），w，（v₁，…，v_n）， 1V|} .對于隨機生成的 {Y₁^'，…，Y_n^'} ，模擬器 Sim_R 經(jīng)ElGamal 公鑰 Δ_Pk 加密后產(chǎn)生的 {EBF₁^'，…，EBF_n^'} 和真實世界執(zhí)行協(xié)議產(chǎn)生 {EBF₁，…，EBF_n} 的不可區(qū)分，因此 .而腐敗方 R 無法區(qū)分根據(jù) {VBF₁^'，…， 和 計算后得到的 {value₁，…，value_n^'} 和協(xié)議執(zhí)行過程中獲得的 {value₁，…，value_n} .模擬器Sim_R{X，∣V∣}={X，（ρk，sk），w^′，（v₁^'，…，v_n^'），∣V∣} ，因此式（7）成立.同理，腐敗方 S_i 執(zhí)行協(xié)議時的真實視圖 View_s^π={Y_i，w，⊥} 和模擬器 Sim_s 模擬 S_i 的視圖 Sim_R{Y_i，⊥} 無法區(qū)分，即式（8）成立.協(xié)議1達到半誠實安全.

定理2協(xié)議2在半誠實模型下安全地輸出查詢用戶在 n 方的交集基數(shù)以及不良信譽情況，且協(xié)議能夠抵抗 n-1 個敵手合謀.

證明從2種情況考慮協(xié)議2中可能發(fā)生的不誠實行為：一種是敵手控制的腐敗方包括查詢方 R ，另一種是不包括查詢方 R .本節(jié)針對此分析協(xié)議2安全性.

情況1存在 Ψ_tΨ_Ψ 個被查詢方 S_i 是腐敗方且查詢方 R 不受敵手控制.

假定 Ψ_t 個腐敗方 S₁，…，S_t 被敵手控制，敵手可獲得腐敗方輸入及協(xié)議執(zhí)行過程產(chǎn)生的參數(shù).構(gòu)建模擬器sin_st 模擬 Ψ_t 個腐敗方 S₁，…，S_t 的視圖，模擬器 sin_st 收到數(shù)據(jù)集 {Y₁，…，Y_t} 、公鑰對 （?_Pk_i，sk_i） 和信譽過濾器 {VBF₁，…，VBF_t} ，為查詢方 R 提供私鉬 sk_i 解密的份額 share_l，i ， i∈[1，t] ，記腐敗方 S₁，…，S_t 執(zhí)行協(xié)議時的真實視圖為 View_Si^π={（Y₁，…，Y_i），（pk₁，…，pk_i），（VBF₁，…，VBF_i），（share_i，⊥，…，share_i，i）} re，t）}.

由于模擬器 Sim_si 控制 個被查詢方，它只能獲得 t 個被查詢方的密鑰份額，且在ElGamal多密鑰加密中，交集用戶信譽值的解密需要全部 n 個被查詢方的聯(lián)合計算，所以模擬器 Sim_si 無法從 t 個腐敗方的聯(lián)合計算中獲得最終的解密結(jié)果.

（20 t 個被查詢方 S₁，…，S_t 在協(xié)議真實交互過程中的視圖表示為 V_iewsi^π ，而模擬器 Sim_si 的視圖為Sim_t{（Y₁，…，Y_t），⊥} .對于隨機生成的元素 （Y₁，…，Y_t） 和 （pk₁，…，pk_i） ，由于EIGamal算法的安全性和隨機性，模擬器 sin_t 生成的 （VBF₁^'，…，VBF_t^'） 和真實協(xié)議中的 （VBF₁，…，VBF_t） 在計算上是不可區(qū)分的.對不同被查詢方 S₁，…，S_t，S_t+1，…，S_n 使用私鑰對密文 C_l，i^' 計算生成的 （share_ι，1^'，…，share_ι，t^'） 和 （share_ι，ι，…， （20share_l，t） 在計算上是不可區(qū)分的.因此： Sim_st{（Y₁，…，Y_t），⊥}≡View_st^π ：

情況2存在 Ψ_tΨ_t 個被查詢方 S_i 是腐敗方且查詢方 R 也是腐敗的.

與以上情況相同，構(gòu)建模擬器 Sim_R，St 模擬腐敗方 R 和 S₁，…，S_t 的視圖.模擬器 Sim_R，St 收到的輸入集為 {X，Y₁，…，Y_t} ，從 S₁，…，S_t 獲取 {VBF₁，…，VBF_t} 以及計算的中間結(jié)果 （C_ι，1，…，C_ι，t） 和 （share_ι，1，…， share_l，t） ，最后輸出結(jié)果為 ，記腐敗方 R 和 S₁，…，S_t 執(zhí)行協(xié)議時的真實視圖為：

模擬器 Sim_R，St 擁有 {pk，（pk₁，sk₁），…，（pk_t，sk_t）} ，但解密 需要 S_t+1，…，S_n 的私鑰（204號 {sk_t+1，…，sk_n} ，由于ElGamal加密算法是基于離散對數(shù)困難問題的，僅通過 Δ_Pk 和 （ρk_?1，sk_?1），…，（ρk_?t，sk_?t） （204號無法分解解密出 C_l，i^' 對應(yīng)的明文，而模擬器 Sim_R，St 生成的 {share_l，1，…，share_l，t ， share_l，t+1^'，…，share_l，n^'} 和

真實協(xié)議執(zhí)行過程中產(chǎn)生的 （share_l，1，…，share_l，t，share_l，t+1^′，…，share_l，n^′） 在密文下無法區(qū)分，敵手也無法從中獲取解密結(jié)果以及用戶信息.因此，Sim.s{（X，Y.…，Y），」w丨 }=Views，

情況3 僅查詢方 R 是腐敗方.

假設(shè)查詢方 R 是腐敗方，意圖獲取被查詢方 S_i 的用戶信譽值，在整個過程中，敵手可以獲得輸入和最終的輸出結(jié)果.腐敗方 R 的真實視圖為 View_R^π ，輸入集為 X ，最終輸出為 此處不再詳細證明，腐敗方無法獲得誠實被查詢方的隱私信息，模擬視圖與真實視圖是不可區(qū)分，因此，

從以上3種情況可以看出，面對半誠實敵手時，敵手無法推斷出誠實方的輸入集，也無法從中間的消息推斷出最終結(jié)果.至此，協(xié)議2半誠實安全的.

定理3在半誠實模型下，協(xié)議3保密地計算了秘密信譽值比較結(jié)果.

證明對任意半誠實敵手構(gòu)造模擬器 Sim_R 和 Sim_s 模擬功能 模擬器Sim，模擬查詢方 R 的行為：由ElGamal算法是語義安全的， output_s（v_l，v_i） 與 f₂（v_l，v_i） 是計算不可區(qū)分的.構(gòu)造模擬器 Sim_s 模擬被查詢方 S 的行為， output₁（v_ι，v_ι） 和 f₁（v_l，v_i） 是計算不可區(qū)分的.

至此，定理3證畢.

5 性能分析與比較

5.1 性能分析

該實驗依賴GMP庫和NTL庫完成EIGamal加密，實驗中選擇1O24bit大素數(shù)、隨機生成32 bit元素進行操作，進行多次重復(fù)實驗并取平均值作為最終結(jié)果.

當設(shè)置查詢方 R 集合為 2⁸ 、被查詢方集合大小為 2¹⁰ ，被查詢方 n 個數(shù)分別設(shè)置為 {2⁴，2⁵，2⁶，2⁷，2⁸，2⁹} 時，協(xié)議1和協(xié)議2運行時間如表1所示.結(jié)果顯示協(xié)議1預(yù)處理耗時，因涉及加密布隆過濾器和生成VBF操作，且參與方數(shù)量增多時，查詢方需要執(zhí)行解密操作時間不受影響，在線計算時間成倍增加.在協(xié)議2中，查詢方需要獲取 n 個參與方提供的解密份額，隨著被查詢方數(shù)量增多，解密耗時增長.由于僅需對生成的VBF執(zhí)行加密操作，協(xié)議2的整體耗時優(yōu)于協(xié)議1，但2種協(xié)議總耗時均在執(zhí)行預(yù)處理階段.

表1不同參與方下協(xié)議各階段運行時間

Tab.1Running time of phases of the agreement under different participants

接著對比協(xié)議1和協(xié)議2各階段運行時間以及在線計算與離線解密時間.如圖1（a）所示，協(xié)議2整體各項執(zhí)行時間均優(yōu)于協(xié)議1，其中預(yù)處理時間占比顯著，導(dǎo)致總耗時增長，原因在于多個被查詢方在該階段對持有的大集合用戶數(shù)據(jù)進行處理.從圖1（b）所示的2種協(xié)議的在線時間和離線解密時間，協(xié)議2雖一開始優(yōu)于協(xié)議1，但隨著被查詢方數(shù)量增多，查詢方 R 離線解密的時間增加，逐漸超過協(xié)議1，因此協(xié)議2更適合參與方數(shù)量有限的查詢.

圖12種協(xié)議各項執(zhí)行時間對比

Fig.1Comparison of implementation time for each of the two agreements

5.2 方案比較

為了與文獻[5]和[7]方案性能對比，設(shè)置大集合方為服務(wù)器，小集合方為客戶端.當參與方數(shù)量為25時，小集合大小設(shè)為 2⁸ 、大集合分別設(shè)為 {2¹⁰，2¹¹，2¹²，2¹³，2¹⁴} 時，各方執(zhí)行時間如表2所示.實驗顯示，被查詢方數(shù)據(jù)量小時，協(xié)議1與現(xiàn)有方案效率相近，協(xié)議2更優(yōu).當被查詢方數(shù)據(jù)量較大時，客戶端執(zhí)行效率均優(yōu)于文獻[5]和[7].協(xié)議1中大集合方的服務(wù)器端執(zhí)行時間雖高于文獻[7]，但在后續(xù)工作中可通過并行執(zhí)行編碼優(yōu)化.

表2與其他方案的實驗時間對比

Tab.2The time of experimental comparison with other schemes

6結(jié)論

本文基于VBF構(gòu)造和多密鉬加解密原理提出2種多方隱私集合交集及秘密數(shù)據(jù)比較協(xié)議，在隱藏查詢方查詢意圖的前提下，保護了被查詢方的用戶身份和隱私數(shù)據(jù).協(xié)議執(zhí)行結(jié)束后，查詢方獲得信譽查詢結(jié)果，而被查詢方對查詢結(jié)果無從得知，最終實現(xiàn)機構(gòu)中用戶信息隱私安全，同時在 Ψ_t 個腐敗方（ χ_tlt;_n 聯(lián)合的情況下，證明協(xié)議達到半誠實敵手的安全，

附錄見電子版（DOI：10.16366/j.cnki.1000-2367.2024.04.13.0001）.

參考文獻

[1]高瑩，王瑋.多方隱私集合交集計算技術(shù)綜述[J].電子與信息學(xué)報，2023，45（5）：1859-1872. GAOY，WANGW.AsurveyofultiartyprivatesetintersectionJJournalofElectronicsamp;InformatioTechology045（5）： 1859-1872.

[2]張萍，蔣琳.隱私保護的網(wǎng)絡(luò)實名制體系研究[J].學(xué)報（自然科學(xué)版），2021，49（6）：91-98. ZHANGP，JANGL.Researchonprivacy-preserving Internetreal-NamesystemJJournalof HenanNormalUniversity（Natural Sci ence Edition），2021，49（6）：91-98.

[3]FREEDMANMJ，NISSIM K，PINKAS B.Eficient private matching and set intersectionC]//Advances in Cryptology-EUROCRYPT 2004.Berlin：Springer Berlin Heidelberg，2004：1-19.

[4] KISSNERL，SONG DPrivacy-preservingsetoperations[C//Advances in Cryptology-CRYPO25.Berlin：SpringerBerlinHeidelberg，2005：241-257.

[5] BAY A，ERKINZ，HOEPMANJH，etalPracticalmulti-partyprivate setintersection protocols[J].IEEE TransactionsonInforation Forensics and Security，2022，17：1-15.

[6] DAVIDSONA，CIC.Aneficienttoolkit forcomputing private SetOperations[C]/Information SecurityandPrivacy.Cham：Springer International Publishing，2017：261-278.

[7] RUANO，YANCW，ZHOUJ，etal.Apracticalmultipartyprivatesetintersectionprotocolbasedonbloomfltersforunbalancedsearios[J].Applied Sciences，2023，13（24） ：13215.

[8] YAOAC.Protocols forsecurecomputations[C]/23rd Anual Symposiumon FoundationsofComputer Science（sfcs1982）.November 3-5，1982.Chicago：IEEE，1982：160-164.

[9] 張靜，何錚，葛炳輝，等.一種高效的百萬富翁問題協(xié)議及其應(yīng)用[J].計算機工程，2021，47（2）：168-175. ZHANGJ，HEZ，GEBH，etalAnefentprotolfrmiloiresprobeanditslicatioJComputerEgining，472）： 168-175.

[10]李順東，王文麗，陳明艷，等.抗主動攻擊的保密比較協(xié)議[J].軟件學(xué)報，2022，33（12）：4771-4783. LI S D，WANGWL，CHENMY，t al.Comparing protocolagainstactiveattacksJ]JournalofSoftware，2233（12）：477-4783.

[11]BLOOMBHSpace/time tradefs inhashcodingwithallowableerorsJ].CommunicationsoftheACM，197o，13（7）：422-426.

[12]DONGCY，CHENL QWENZK.Whenprivate setintersection metsbigdata：aneficientandscalableprotocolC//Proceedingof the2013ACMSGSACConferenceonComputeramp;CommunicationsSecurity-CCS13.November4-8，2013.Berlin：ACM，2013789-800.

[13]EGAMALT.ApublickeycryptosystemandasignatureschemebasedondiscretelogarithmsC]//Advances in Cryptology.Berlin： Springer Berlin Heidelberg，1985：10-18.

[14]YNGXY，ZHAOYQ，ZHOUSF，etalAlghtweightdelegatedprvatesetintersectioncardinalityprotocolJComputertaddsamp; Interfaces，2024，87：103760.

[15]LINDELLY.Howtosimulateit-atutorialonthesimulationproftechiqueM.TutorialsontheFoundationsofCryptography：Dedicated to Oded Goldreich，[S.l.]：Springer，2017.

Multiparty privacy set intersection and secret reputation value comparison protocols

Li Gonglia'b，F(xiàn)an Yuna，Ma Jingwena

（a.ColegeofComputerandInformationEngineeing；b.KeyLaboratoryofArtificialIntellgenceandPersonalizedLearningin Education of Henan Province，Henan Normal University，Xinxiang 453oo7，China）

Abstract：Multiparty private set intersection（MPSI），as adata security protection computation technology in th fieldof secure computation，supports thecomputationof the intersectionofmultipleparticipant datasets withoutrevealinganyparticipant's privacy，whichcanbeachieved byusing homomorphicencryption，oblivious transfer，andother technical means.However，theexisting MPSI protocols basedon homomorphic encryptionhaveproblems such as lowcomputational eficiencyand manyroundsofinteraction，andcannotcomputetheintersectionofusersconfidentialdatathrough interaction.Therefore，this article first proposes an n -party intersection users secret reputation value comparison protocol， based on bloom filters and the ElGamalalgorithm.Furthermore，imingattheproblemoffailedqueryintersection，auser intersectioncardinalityprotocolis proposed basedonreputation value filters andmulti-key encryption and decryption，andthe evaluation of multi-partysecret reputation values iscompleted.Experimentalresults show thatthe two protocols proposed in the study satisfysemi-honest security，can resist coalitions of n-1 participants，and have better execution time than other schemes.

Keywords：multi-party private set intersection； secret reputation comparison;reputation threshold comparison； multi ple secret reputation value comparison；multiparty intersection cardinality

圖S1 插入元素 {x₁，x₂，x₃} 到BF

圖S2插入元素x到GBF Fig.S2 Insert element x_i into GBF

圖S3多方隱私集合交集的理想功能

Fig.S3 Multi-party private set intersection ideal functions