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

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

1 相关工作

现有门限隐私集合的研究主要分为两种, 一种是数据集门限 (multi-party threshold private set intersection, MP-
TPSI) [27−32] , 各个参与方私有集合中, 数据元素的交集数量达到门限值. 张恩等人 [27] 采用混淆布隆过滤器和秘密共
享的方式实现了数据集门限测试方法, 设计了一种多方门限隐私集合交集协议. Liu 等人 [28] 将确定型门限通过 GS
协议转化成概率型门限, 设计了一种概率门限测试协议, 使得协议性能显著提高. Mohanty 等人 [29] 提出了一种两方
抗量子的 TPSI 协议, 通过可信第三方生成抗量子密钥来完成两方之间的隐私集合交集操作, 文中仅提供了理论基
础, 并未实现. Ghosh 等人 [30] 提出了一种 TPSI 协议, 基于加性同态加密设计门限测试方法, 使得协议的通信复杂度
仅依赖于阈值 t. Badrinarayanan 等人 [31] 将 Ghosh 等人 [30] 的工作由两方拓展到多方, 研究了多方设置下 ( N > 2) 门
限测试的通信复杂度. Ghosh 等人 [32] 将 TPSI 协议分为隐私集合交集基数测试 (private intersection cardinality test,
PICT) 和 PSI 两个部分, 通过通用安全计算框架实现 PICT 功能, 实现多方设置下更好的通信复杂度.
另一种是参与方数量门限 (TMP-PSI) [17,24,26,33] , 拥有相同数据元素的参与方数量达到门限值, 则该数据元素作
为交集输出给指定方. Bay 等人 [17] 使用同态加密和加密布隆过滤器结合的方式设计了一种判断参与方门限的方
法. 这个协议的性能瓶颈在于同态加密和加密布隆过滤器设计的门限测试, 在交互过程中的通信开销随着数据集
的增多呈指数型增长, 使得协议的运行效率受到较大影响. Chandran 等人 [24] 提出了一个 Quorum PSI 协议, 他们采
t
用了电路的方式实现了此功能, 选择一个参与方 P 1 作为领导者, P 1 拥有的某个数据元素 x, 如果在不少于 个参与
方的集合中存在, 则作为交集输出给 P 1 , 此方案仅有领导者 P 1 得到输出, 其他参与方不得到任何输出. Chandran
等人使用通用电路框架构造协议, 因此随着数据集和参与方数量的增多, 需要生成大量的三元组以及更多的通信
轮数, 且无法适应门限值的变化. Mahdavi 等人 [26] 采用多次执行多方 PSI 技术实现超阈值隐私集合交集协议, 每
N N 为
次 PSI 协议仅有一个参与方可以得到自己集合中满足条件的元素, 想要所有参与方都得到输出需要执行 (
参与方数量) 次多方 PSI 协议, 随着参与方数量的增多, 执行多方 PSI 次数过多, 无法实现有效拓展. 魏立斐等人 [33]
提出了一个半诚实模型下高效的双云辅助超阈值隐私集合交集协议, 此协议额外引入第三方云的强大算力, 将复
O(n(N logn/t) ), 随着门限值 的增加, 协议重
2t
t
杂的重构操作交给第三方云来辅助计算. 在重构阶段计算复杂度为
构阶段计算开销增长过快, 导致协议整体运行效率下降.
本文构造了两种门限多方隐私集合交集协议, 第 1 种协议仅有一个指定参与方获取自己数据集合中达到门限
的交集信息. 第 2 种拓展门限多方隐私集合交集协议, 实现了多参与方获取私有集合中的交集元素, 除此以外得不
到其他任何信息, 保证了协议的安全性, 如图 2 所示.

服务器
X s ={1,2,3,4}

X 1 ={1,2,3,6} X 4 ={4,5,6,7}
T=3
{1,2,6} {5,6,7}
用户 1 用户 4
X 2 ={1,2,5,7} {2,5,6,7}
{1,2,5,7}
X 3 ={2,5,6,7}

用户 2
用户 3
图 2 拓展门限多方 PSI 示意图