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

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

本文的主要贡献如下.
(1) 提出了一种兼顾通信轮数与计算开销的参与方门限测试方法, 设计的门限测试方案采用弹性秘密共享和
不经意键值对存储, 实现了任意门限下的高效计算. 秘密分发者在本地生成所需的秘密份额, 仅需要一轮通信就可
以完成所有秘密份额的发送, 参与方通过秘密份额隐藏自己的私有数据集合后执行重构操作, 不仅保护了交集以
外其他信息, 而且能够有效减少通信轮数和计算开销.
(2) 针对现有的 TMP-PSI 协议只能单参与方获取交集, 无法满足多参与方获取私有集合中交集信息的需求,
本文通过对弹性秘密共享份额分发阶段进行拓展, 实现了多参与方获得私有集合中达到门限值的交集信息, 相比
较于第 1 种协议不需要额外增加通信轮数. 本文设计的 ETMP-PSI 协议与 Mahdavi 等人 [26] 和魏立斐等人 [33] 提出
(
的超阈值隐私集合交集协议相比, 重构方计算复杂度由 O(nNtlognλ) 降为 O(bNλ) n 是数据集合大小, N 是参与方
数量, t 是门限值, λ 是计算安全参数).
(3) 通过实验测试了两种协议的性能, 从计算和通信复杂度方面、不同数据集大小和不同参与方数量等多种
情况下给出了详细的分析和实验数据, 实验结果表明两种方案与现有的方案相比拥有更好的性能.

2 基础知识

本节介绍本文协议中用到的相关技术以及安全模型.
2.1 布谷鸟哈希和朴素哈希表
布谷鸟哈希 (cuckoo hash) 技术最早于 2001 年由 Pagh 等人 [34] 提出的一种哈希技术, 不仅可以高效地构造哈
希表, 而且数据元素的插入算法性能较高. 布谷鸟哈希表是通过多个 (通常是 2、3 或 4 个) 不同的哈希函数实现
的, 其特性是哈希表中的每个位置 ( bin) 只存储一个数据元素, 具体流程如下所示.
λ
∗
T
(1) 初始化一个长度为 b 的哈希表 , 选取 k 个 hash : {0,1} → {0,1} 函数 H 1 ,...,H k .
bin 中只允许存储一个
(2) 使用某个哈希函数 H i (·), i ∈ [1,k] 将数据元素 x 映射到哈希表 T 的 H i (x) 位置, 每个
数据元素. 如果此位置不为空则踢出此位置原有的数据元素, 将其放入待插入队列中重新插入.
(3) 当上述替换操作达到一定次数后, 则将未插入的数据元素放置在额外的存储空间 ( stash) 中.
(4) 对于表中的空位置使用随机值填充.
stash 的布谷鸟哈希表, 如图 3 所示. 在布谷鸟哈希中, 有多个哈希函数 (图 3 中使用两个哈希函数
本文采用无
H 1 和 H 2 ) 和数据元素 (图 3 中的 x 1 、 、 、 ).
x 3
x 2
x 4

H 1 (x 1 )
x 1 x 1 x 1
H 1 (x 2 ) H (x )
1 5 x
x 2 x 2 5 x 5
产生碰撞
H 1 (x 3 )
x 3 x 3 x 3
弹出
H 2 (x )
x 2 x 2
2
H 1 (x 4 )
x 4
x 4 处理冲突 x 4
图 3 布谷鸟哈希示意图

,
初始映射: 首先使用哈希函数将数据元素映射到哈希表中的位置, x 1 使用 H 1 映射到位置 H 1 (x 1 ) x 2 使用 H 1 映
,
,
射到位置 H 1 (x 2 ) x 3 使用 H 2 映射到位置 H 2 (x 3 ) x 4 使用 H 2 映射到位置 H 2 (x 4 ).
冲突处理: 当有新的数据元素 (图 3 中的 x 5 ) 要插入时, 它首先使用哈希函数 H 2 映射到位置 H 2 (x 5 ). 然而, 这个
位置已经被占用 (图 3 中显示有冲突). 为了解决冲突, 被占用位置上的数据元素 x 2 会被 “踢出”, 并通过另一个哈
希函数 H 1 重新映射到新的位置 H 1 (x 2 ). 如果新的位置仍然有冲突, 这个过程会继续, 直到找到一个空的位置或者
达到一定的迭代次数限制.
Pinkas 等人 [14] 通过实验分析出哈希函数个数 k 和哈希表长度 b 的最佳关系, 确定了无 stash 情况下哈希函数