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

1830 软件学报 2026 年第 37 卷第 4 期

和安全参数 λ.
(1) 在预处理阶段, Sim i 根据 P i , i ∈ [3,N] 的输入 X i 构造朴素哈希表 TS i .
i ′
(2) 在线阶段, Sim i 均匀随机采样 b 个秘密 s , m ∈ [1,b], 计算秘密份额 {s }.
′
m m
′
(3) Sim i 抽样一个洗牌规则 seed 执行洗牌算法, 获得输出 D .
i
(4) Sim i 输出 P i , i ∈ [3,N] 的视图为 (X i , s ,D ).
i ′
′
i
m
i ′ i P i , i ∈ [3,N] 与其他诚实
模拟器模拟出的 {s } 与真实协议执行过程中 P 2 随机抽样的 {s } 是计算不可区分的.
m
m
′ seed 的选择是参与方私有的,
参与方进行洗牌算法, 只需证明输出值 D 的隐私性即可, 秘密洗牌算法中 P i , i ∈ [3,N]
i
′
不知道其他参与方的洗牌规则使得 P i , i ∈ [3,N] 无法区分模拟器在理想模型中随机生成的 D 和真实协议中执行
i
打乱洗牌算法得到的 D i . 因此秘密分发者 P i , i ∈ [3,N] 的视图在理想世界与现实世界上计算不可区分. 即:

λ c π
{Sim (1 ,X i )}≡{View ((X 1 ,...,X N ),λ)} (19)
i i
4 拓展的门限多方隐私集合交集协议
4.1 协议构造
拓展的门限多方隐私集合交集协议是在 TMP-PSI 协议的基础上对秘密份额共享部分进行拓展, 实现了多参
与方获得各自私有集合中达到交集的数据元素. 本节继续采用表 1 中定义的符号, 协议流程图如图 7 所示.

本地计算
1-1. 生成朴素哈希表
并为每个 bin
生成秘密 s
2. 分发秘密份额和 2. 分发秘密份额和
原始秘密 s 秘密分发者 原始秘密 s
3. 根据哈希表编码
OKVS 数据结构作为
输入

4. 得到打乱顺序的 4. 得到打乱顺序的
OKVS 结构 OKVS 结构
秘密洗牌
本地计算 本地计算
1-2. 生成朴素和 1-2. 生成朴素和
布谷鸟哈希表 3. 根据哈希表编码 3. 根据哈希表编码 布谷鸟哈希表
OKVS 数据结构作为 OKVS 数据结构作为
输入 输入
5. 本地解码 5. 本地解码
秘密重构者 6. 执行秘密重构算法 6. 执行秘密重构算法 秘密重构者
7. 得到交集结果 7. 得到交集结果
重构算法
图 7 ETMP-PSI 协议流程图 (以 3 个参与方为例)

协议 2. 拓展的门限多方隐私集合交集协议 ( Π N,n,t ).
ETMP-PSI
参数: 与协议 1 参数设置相同.
选择 P 1 作为秘密分发参与方, P j , j ∈ [2,N] 作为秘密重构者, 拓展协议中没有普通参与方.
预处理阶段如下.
k
(1) P 1 输入集合元素 X 1 由 个哈希函数生成朴素哈希表 TS 1 P 1 作为秘密分发者为 TS 1 中的每个 bin 生成秘
.
密 s, 得到 b 个秘密值 s m , m ∈ [1,b] 并执行 F RSS-Gen 秘密份额生成算法, 每个秘密对应插值出一个 t −1 次多项式