摘要
多方隐私集合交集(Multiparty Private Set Intersection,MPSI)协议允许多个参与方各自持有私有集合,在不泄露除交集以外任何信息的前提下,安全计算所有集合的交集,在泄露凭证检查、金融反欺诈和联邦学习等领域具有广泛应用。然而,现有非平衡隐私集合交集协议主要针对两方参与场景,缺乏针对多方参与场景的高效解决方法。为了解决MPSI及其变体协议在非平衡数据集上效率低下的问题,本文提出一种非平衡双中心零共享的方法。该方法结合零共享和不经意键值存储技术,将多方非平衡计算归约为两方非平衡计算,有效降低了通信和计算开销。然后,通过将该方法和两方非平衡隐私集合交集及其变体协议相结合,构建了一种新的高效且可扩展的多方非平衡隐私集合交集(Multiparty Unbalanced Private Set Intersection, MUPSI)及其变体协议。实验结果表明,在相同条件下,客户端的集合规模为2^(10),服务器端的集合规模为2^(27)时,本文提出的MUPSI协议的服务器端在线阶段耗时比目前最优的协议缩短约20%。此外,在32个参与方的场景下,客户端的集合规模为2^(10),服务器端的集合规模为2^(27)时,客户端在线阶段耗时约10秒,验证了该协议在大规模参与方以及集合规模差异显著场景下的有效性。
Multiparty Private Set Intersection(MPSI)protocols enable multiple participants to securely compute the intersection of their private datasets without revealing any extra information beyond the intersection itself,serving as a critical primitive for privacy-preserving data collaboration.Such protocols hold extensive practical application value.In compromised credential checking scenarios,they assist platforms in cross-verifying leaked account data while preventing the exposure of complete user lists.In financial anti-fraud work,they identify cross-institutional fraud rings by matching and analyzing suspicious transaction records across different banks.In the field of federated learning,they realize effective alignment of sample spaces for distributed training data,all while safeguarding data privacy throughout the process.However,existing unbalanced Private Set Intersection(PSI)protocols mainly focus on two-party scenarios,where one party holds a large-scale dataset and the other holds a small-scale dataset.In multi-party unbalanced scenarios(e.g.,one server holds massive data while multiple clients each hold only small datasets),directly applying traditional MPSI schemes usually encounters significant efficiency bottlenecks.Although some existing works have optimized MPSI protocols for unbalanced scenarios,their performance still degrades rapidly when there is a large difference in the size of datasets among participants.To address the inefficiency of MPSI and its variant protocols on unbalanced datasets,we propose an Unbalanced Bicentric Zero-Sharing(UBZS)method.This method combines the zero-sharing mechanism with Oblivious Key-Value Store(OKVS)technology.It designates two core participants as Pivot and Leader respectively,encodes the shared values using OKVS,and then distributes the encoded values to all participants.By converting multi-party unbalanced computation tasks into two-party interactions between the Pivot and the Leader,this method effectively eliminates redundant operations for ordinary clients and significantly reduces the overall communication and computational overhead.Furthermore,by integrating this bicentric framework with the optimized two-party Unbalanced Private Set Intersection(UPSI)and its variants,we construct an efficient and scalable Multi-Party Unbalanced Private Set Intersection(MUPSI)protocol and its variants(e.g.,supporting the computation of the cardinality of multiparty unbalanced private set intersection).The experimental results show that under the same conditions,when the client’s set size is 2^(10) and the server’s set size is2^(27),the client online phase time consumption of the proposed MUPSI protocol is about 20%shorter than that of the current optimal protocol.Moreover,when the client’s set size is 2^(10) and the server’s set size is 2^(27),in a scenario with 32 participants,the client’s online execution time is approximately 10 seconds.These results validate the protocol’s effectiveness in scenarios with a large number of participants and significant differences in set sizes.To further verify the efficiency of the UBZS method,which serves as the core technology of the MUPSI protocol,we conducted comparative experiments with the previously proposed Balanced Bicentric Zero-Sharing(BZS)protocol under Local Area Network(LAN)conditions.The experiments focused on the variation of time consumption as the size of the server-side dataset increased(in a scenario with one server and multiple clients).In the experiments,the server-side set size was sequentially set to 220,222,224 and 2^(27).The results show that the server-side time consumption of the BZS protocol was 0.053 seconds,0.176 seconds,0.622 seconds,and 4.675 seconds respectively,exhibiting a significant upward trend with the increase in data scale.In contrast,the UBZS method consistently maintained low and stable computational overhead under the same conditions,with corresponding time consumption values of 0.001 seconds,0.001 seconds,0.002 seconds,and 0.004 seconds.This result indicates that UBZS effectively avoids the significant time growth exhibited by BZS when processing largescale datasets.It further verifies the efficiency of the unbalanced optimization design in reducing computational overhead and provides important technical support for the effectiveness of the MUPSI protocol in unbalanced multi-party scenarios.
作者
张恩
李金磊
郑东
禹勇
刘登辉
ZHANG En;LI Jin-Lei;ZHENG Dong;YU Yong;LIU Deng-Hui(College of Computer and Information Engineering,Henan Normal University,Xinxiang,Henan 453007;Key Laboratory of Artificial Intelligence and Personalized Learning in Education of Henan Province,Xinxiang,Henan 453007;National Engineering Laboratory of Wireless Security Technology,Xi’an University of Posts and Telecommunications,Xi’an 710121;School of Artificial Intelligence and Computer Science,Shaanxi Normal University,Xi’an 710062)
出处
《计算机学报》
2026年第1期193-210,共18页
Chinese Journal of Computers
基金
国家密码科学基金(2025NCSF02025)
国家自然科学基金联合基金重点项目(U24B20149,U23A20302)、国家自然科学基金(No.62372157)
陕西省重点研发计划重点产业创新链项目(2024GX-ZDCYL-01-09)资助。
关键词
多方非平衡隐私集合交集
不经意键值存储
零共享
全同态加密
布谷鸟哈希
multiparty unbalanced private set intersection
oblivious key-value store
zero-sharing
fully homomorphic encryption
cuckoo hashing
