Efficient Scalable Multi-Party Private Set Intersection(-Variants) from Bicentric Zero-Sharing

Multi-party private set intersection (MPSI) allows n(n = 3) 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 2²⁰ elements each, our protocol is 46.4× faster in the LAN setting, 18.3× faster in WAN setting, and requires 24.7× 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 2²⁰ elements each, our MPSI and MPSI-CA protocol requires only 4.557s and 16.02s in the LAN setting, respectively.