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

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

3 门限多方隐私集合交集协议

本节提出了一种基于弹性秘密共享的门限多方隐私集合交集协议, 协议中符号的定义见表 1. 根据第 2.1 节给
stash 的布谷鸟哈希表生成方式. 预处理阶段秘密分发者需要根据协议将自己的
出的布谷鸟哈希定义, 本文采取无
数据元素哈希到朴素哈希表并为每个 bin 关联对应的秘密份额. 在线阶段需要秘密重构者根据自己的数据元素去
查询获得份额值进行重构, 协议流程图如图 6 所示, 具体协议如下.

表 1 协议符号表

符号 含义 符号 含义
t 门限值 m ∈ [1,b] 哈希表的索引
N 参与方数量 s m 第 m 个 bin 生成的秘密
n 私有数据集大小 s m j 发给参与方 j 的秘密份额
λ 计算安全参数 P i 参与方 i
σ 统计安全参数 X i 参与方 i 的私有数据集
k 构造哈希表的哈希函数数量 D i 参与方 i 编码的OKVS结构
生成哈希表的哈希函数 i 的朴素哈希表
h k TS i 参与方
bin 哈希表放置数据的位置 TC i 参与方 i 的布谷鸟哈希表
b 哈希表的长度 ( bin 的数量) q 朴素哈希表每个 bin 中的位置索引
H(·) 单向哈希函数 η 秘密共享需要添加的冗余值数量
F 整数域 stash 布谷鸟哈希暂存区
f(·) 秘密共享插值出的多项式 I 交集集合

本地计算
1-2. 生成朴素哈希表
并为每个 bin
生成秘密 s

2-2. 分发秘密份额和 2-1. 分发秘密份额
原始秘密 s 秘密分发者

重构算法
3. 根据哈希表编码
OKVS 数据结构作为
7. 得到交集 输入
结果
6. 执行秘密重构算法
本地计算 本地计算
1-1. 生成布谷鸟 1-3. 生成朴
哈希表 素哈希表
3. 根据哈希表编码
5. 本地解码 4. 得到打乱顺序的
秘密重构者 OKVS 结构 OKVS 数据结构作为 其他参与方
秘密洗牌 输入

图 6 TMP-PSI 协议流程图

3.1 协议构造
协议 1. 基于弹性秘密共享的门限多方隐私集合交集协议 ( Π N,n,t ).
TMP-PSI
参数: N 个参与方 P i , i ∈ [1,N], 每个参与方的私有数据集合 X i 的大小为 n, 选择一个单向哈希函数 H : {0,1} →
∗
λ ∗ λ
{0,1} , 门限值设置为 t, 所有参与方共同商议 k 个哈希函数 h k : {0,1} → {0,1} 用于构造哈希表.