| 摘要: |
| (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 = 216的三方场景下运行时间为6.4 s (TMP-PSI)和8.7 s (ETMP-PSI), 与现有的门限多方隐私集合交集协议相比, 重构方和分发方的通信复杂度由O(nNtlognλ)降为O(bNλ). |
| 关键词: 门限多方隐私集合交集协议 通信轮数 计算开销 弹性秘密共享 不经意键值对存储 |
| DOI：10.13328/j.cnki.jos.007434 |
| 分类号:TP309 |
| 基金项目:国家自然科学基金(62372157) |
|
| Threshold Multi-party Private Set Intersection Protocol Balancing Communication Rounds and Computational Overhead |
|
ZHANG En1,2, HUANG Yu-Chen1, ZHENG Dong3, YU Yong4
|
|
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 obtain the intersection. To address these issues, this study proposes a threshold testing method based on robust secret sharing (RSS) and a TMP-PSI scheme combined with oblivious key-value store (OKVS), which effectively reduces both computational overhead and the number of communication rounds. To meet the demand for multiple participants to access the intersection information from their private sets, this study also proposes a second extended threshold multi-party private set intersection (ETMP-PSI) protocol, which modifies the share distribution method. Compared to the first scheme, the secret distributor and secret reconstructor do not incur additional communication rounds or computational complexity, allowing multiple participants to obtain the intersection elements from their private sets. The proposed protocol runs in 6.4 seconds (TMP-PSI) and 8.7 seconds (ETMP-PSI) in a three-party scenario with a dataset size of n=216. Compared to existing threshold multi-party private set intersection protocols, the communication complexity between the reconstructor and distributor is reduced from O(nNtlognλ) to O(bNλ). |
| Key words: threshold multi-party private set intersection (TMP-PSI) protocol communication round computational overhead robust secret sharing oblivious key-value store (OKVS) |
