Release time:2025-03-31

Hits:

DOI number:10.1145/3658644.3690245

Journal:Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security

Place of Publication:Salt Lake City, UT, USA

Key Words:Private Set Intersection (PSI); Zero-Sharing

Abstract:Multi-party private set intersection (MPSI) allows n (ngeq3) participants, each holding a dataset of size m, to compute the intersection of their sets without revealing any additional information. We extract a primitive called bicentric zero-sharing, which can reduce MPSI to two-party PSI between two central participants named Pivot and Leader. We introduce an efficient instantiation of bicentric zero-sharing, which involves a round of sharing and reconstruction of an oblivious key-value store (OKVS) object. We then combine this construction with two-party PSI to propose a new efficient scalable MPSI protocol. We also propose protocols for computing MPSI variants based on bicentric zero-sharing, such as multi-party private set intersection cardinality (MPSI-CA) and multi-party threshold private set intersection (MTPSI). Our protocols are mainly based on symmetric-key operations, and the communication complexity of each participant is at most O(n+m). The security of our protocols relies on the assumption that Leader and Pivot do not collude, which can be applicable in many scenarios. In this case, our protocols are secure against arbitrary collusion (except Leader and Pivot) in the semi-honest model. Moreover, our protocols are secure against up to n-2 malicious Clients (participants except Leader and Pivot) in the random oracle model. All these protocols realize the scalability with the number of participants.We demonstrate the scalability of our protocols with an implementation and a comparison with the state-of-the-art MPSI. Experiments show that when computing MPSI for 15 participants with datasets of 220 elements each, our protocol is 46.4x faster in the LAN setting, 18.3x faster in WAN setting, and requires 24.7x less communication cost compared to the state-of-the-art in CCS'21 (by Nevo et al.), and the improvement becomes more significant as the number of participants and set size increases. To the best of our knowledge, ours are the first protocols that report on more than 100 participants. For 140 participants with datasets of 220 elements each, our MPSI and MPSI-CA protocol requires only 4.557s and 16.02s in the LAN setting, respectively.

Co-author:Yuanchao Luo, Longxin Wang, Xiang Liu, Lin Qi, Wei Wang, Mengmeng Zhou

First Author:Ying Gao

Indexed by:会议论文

Correspondence Author:Ying Gao

Page Number:4137–4151

ISSN No.:9798400706363

Translation or Not:no

Date of Publication:2024-12-09