Page 388 - 《软件学报》2026年第4期

张恩 等: 兼顾通信轮数与计算开销的门限多方隐私集合交集协议 1829

证明: 首先验证该协议在执行过程中的正确性, 然后证明该协议在半诚实模型下的安全性.

● 正确性. 份额分发阶段, 秘密重构者 P 1 使用 k 个哈希函数映射出布谷鸟哈希表 TC 1 , 其他参与方 P i , i ∈ [2,N]
.
使用 k 个哈希函数映射出朴素哈希表 TS i [m], m ∈ [1,b] P 1 需要在与其他参与方交互过程中得到 t −1 个正确的份
f (·). 秘密重构者解密操作如下.
′
额即可重构秘密多项式
D i , 将布谷鸟哈希表中的数据元素作为查询元素
在线阶段, 当 P 1 得到其余 N −1 个参与方 P i 编码的数据结构
输入, 每个数据元素对应解码得到 N −1 个份额值.
rs 为解
i
当 TC 1 [m] ⊂ TS i [m], 即存在 TS i [m][q] = TC 1 [m]. 参与方 P 1 可以通过查询得到正确的秘密份额值, 令
m
码 D i 得到的结果:

i
rs = F Decode (D i ,TC 1 [m])
m
i
i
= F Decode (F Encode (k ,v ),TC 1 [m])
m m
i
= F Decode (F Encode (TS i [m][q],TS i [m][q]⊕ s ),TC 1 [m])
m
= TS i [m][q]⊕ s i (15)
m
参与方 P 1 异或自己的查询元素即可解出正确份额:

i
i
s = rs ⊕TC 1 [m] (16)
m
m
● 安全性. 证明协议 Π N,n,t 在半诚实模型下是安全的. 模拟器分别模拟腐败的秘密重构者 P 1 , 腐败的秘密分
TMP-PSI
发者 P 2 和腐败的普通参与方 P i , i ∈ [3,N] 的视图.
第 1 种情况, 模拟器 ( Sim 1 ) 模拟腐败的秘密重构者 P 1 的视图. Sim 1 收到来自 P 1 的输入 X 1 和安全参数 λ 以及
交集 I.
(1) 在预处理阶段, Sim 1 根据 P 1 的输入 X 1 构造布谷鸟哈希表 TC 1 .
(2) 在线阶段, Sim 1 均匀随机采样 b 个秘密 s , m ∈ [1,b] 以及 2N −t 个随机点值执行弹性秘密共享生成算法,
′
m
N ′
1 ′
′
计算秘密份额 {s ,..., s , s N+1 ′ ,..., s 2N−t ′ } 和 H(s ) 其中 m ∈ [1,b].
m m m m m
N ′
1 ′
(3) Sim 1 根据交集 均匀随机抽样 n−|I| 个随机值 X r = {x 1 , x 2 ,..., x n−|I| } , 计算 D ← F Encode ({I,X r },{s ,..., s ,
′
I
m
i
m
s N+1 ′ ,..., s 2N−t ′ }) .
m
m
N ′
1 ′
1 ′
N ′
(4) Sim 1 输出 P 1 的视图为 (X 1 ,{s ,..., s , s N+1 ′ ,..., s 2N−t ′ },H(s ),D ), 其中 {s ,..., s , s N+1 ′ ,..., s 2N−t ′ } 和 H(s ) 模
′
′
′
m m m m m i m m m m m
′
拟的是真实协议中 P 2 发送给 P 1 的消息, D , i ∈ [2,N] 模拟的是真实协议中参与方 P i 发送给 P 1 的消息.
i
1 ′
N
N ′
1
模拟器模拟出的 {s ,..., s , s N+1 ′ ,..., s 2N−t ′ } 与真实协议执行过程中 P 2 随机抽样的 {s ,..., s , s N+1 ,..., s 2N−t } 是计
m
m
m
m
m
m
m
m
算不可区分的. H(s ) 模拟的是秘密分发者 P 2 发送给重构者 P 1 的原始秘密, 由于 H(·) 的单向不可逆性, 保证了重
′
m
′ P i 发
.
构方 P 1 无法区分模拟器生成的秘密 H(s ) 和真实协议执行过程中产生的 H(s m ) D i , i ∈ [2,N] 是其他参与方
m
P 1 的 OKVS P 1 没有其他参与方的输入, 基于 OKVS P 1 在理想世界
给重构方 数据结构, 由于 编码的安全性保证了
′ D i , i ∈ [2,N] 是不可区分的. 因此秘密重构者理想世界的视图与现实世界视
获得的 D , i ∈ [2,N] 与真实世界获得的
i
图是计算不可区分的, 即:

λ c π
{Sim (1 ,X 1 ,I)}≡{View ((X 1 ,...,X N ),λ)} (17)
1 1
第 2 种情况, 模拟器 ( Sim 2 ) 模拟腐败的秘密分发者 P 2 的视图. Sim 2 收到来自 P 2 的输入 X 2 和安全参数 λ.
(1) 在预处理阶段, Sim 2 根据 P 2 的输入 X 2 构造朴素哈希表 TS 2 .
(2) 在线阶段, Sim 2 抽样一个洗牌规则 seed 执行洗牌算法, 获得输出 D .
′
2
(3) Sim 2 输出 P 2 的视图为 (X 2 ,D ).
′
2
′ seed 的选择是参与
P 2 与其他诚实参与方进行洗牌算法, 只需证明输出值 D 的隐私性即可, 秘密洗牌算法中
2
′
方私有的, P 2 不知道其他参与方的洗牌规则使得 P 2 无法区分模拟器在理想模型中随机生成的 D 和真实协议中执
2
行打乱洗牌算法得到的 D 2 . 因此秘密分发者 P 2 的视图在理想世界与现实世界上计算不可区分. 即:

λ c π
{Sim 2 (1 ,X 2 )}≡{View ((X 1 ,...,X N ),λ)} (18)
2
第 3 种情况, 模拟器 ( Sim i ) 模拟腐败的普通参与者 P i , i ∈ [3,N] 的视图. Sim i 收到来自 P i , i ∈ [3,N] 的输入 X i