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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(4):1819−1837 [doi: 10.13328/j.cnki.jos.007434] [CSTR: 32375.14.jos.007434] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
兼顾通信轮数与计算开销的门限多方隐私集合交集协议

张 恩 1,2 , 黄昱晨 1 , 郑 东 3 , 禹 勇 4

1
(河南师范大学 计算机与信息工程学院, 河南 新乡 453007)
2
(河南省教育人工智能与个性化学习重点实验室, 河南 新乡 453007)
3
(无线网络安全技术国家工程实验室 (西安邮电大学), 陕西 西安 710121)
4
(陕西师范大学 计算机科学学院, 陕西 西安 710119)
通信作者: 张恩, E-mail: zhangenzdrj@163.com
摘 要: (t, N) 门限多方隐私集合交集协议 (threshold multi-party private set intersection, TMP-PSI) 允许当指定参与
方的集合元素 x 在其余不少于 t–1 (t＜N) 个参与方的私有集合中出现时, 数据元素 x 作为交集结果输出, 在提案投
票、金融交易威胁识别、安全评估等场景具有广泛应用. 现有的门限多方隐私集合交集协议运行效率低、通信轮
数多且只能由某一个指定参与方获取交集. 针对这些问题, 设计一种基于弹性秘密共享的参与方门限测试方法, 结
合不经意键值对存储 (oblivious key-value store, OKVS) 提出一种 TMP-PSI 方案, 能够有效减少计算开销和通信轮
数. 为了满足多参与方获取私有集合中交集信息的需求, 提出第 2 种拓展门限多方隐私集合交集 (extended
threshold multi-party private set intersection, ETMP-PSI) 协议对份额分发方式进行改变, 与第 1 种方案相比, 秘密分
发者和秘密重构方没有额外增加通信轮数和计算复杂度, 实现了多参与方获取私有集合中的交集元素. 所设计的
协议在数据集合大小为 n = 2 的三方场景下运行时间为 6.4 s (TMP-PSI) 和 8.7 s (ETMP-PSI), 与现有的门限多方
16
隐私集合交集协议相比, 重构方和分发方的通信复杂度由 O(nNtlognλ) 降为 O(bNλ).
关键词: 门限多方隐私集合交集协议; 通信轮数; 计算开销; 弹性秘密共享; 不经意键值对存储
中图法分类号: TP309

中文引用格式: 张恩, 黄昱晨, 郑东, 禹勇. 兼顾通信轮数与计算开销的门限多方隐私集合交集协议. 软件学报, 2026, 37(4): 1819–1837.
http://www.jos.org.cn/1000-9825/7434.htm
英文引用格式: Zhang E, Huang YC, Zheng D, Yu Y. Threshold Multi-party Private Set Intersection Protocol Balancing
Communication Rounds and Computational Overhead. Ruan Jian Xue Bao/Journal of Software, 2026, 37(4): 1819–1837 (in Chinese).
http://www.jos.org.cn/1000-9825/7434.htm

Threshold Multi-party Private Set Intersection Protocol Balancing Communication Rounds
and Computational Overhead
1,2 1 3 4
ZHANG En , HUANG Yu-Chen , ZHENG Dong , YU Yong
1
(School of Computer and Information Engineering, Henan Normal University, Xinxiang 453007, China)
2
(Key Laboratory of Artificial Intelligence and Personalized Learning in Education of Henan Province, Xinxiang 453007, China)
3
(National Engineering Laboratory of Wireless Network Security Technology (Xi’an University of Posts and Telecommunications), Xi’an
710121, China)
4
(School of Computer Science, Shaanxi Normal University, Xi’an 710119, China)
Abstract: The (t, N) threshold multi-party private set intersection (TMP-PSI) protocol allows a given party’s data element x to appear in
the private sets of no fewer than t–1 other parties. The data element x is then output as the intersection result, which is widely applied in
scenarios such as proposal voting, financial transaction threat identification, and security assessment. Existing threshold multi-party private
set intersection protocols suffer from low efficiency, high communication rounds, and a limitation that only a specific participant can

* 基金项目: 国家自然科学基金 (62372157)
收稿时间: 2024-08-02; 修改时间: 2024-11-22; 采用时间: 2025-03-17; jos 在线出版时间: 2025-07-30
CNKI 网络首发时间: 2025-07-31