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

DOI码：

10.1145/3658644.3690245

发表刊物：

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

刊物所在地：

Salt Lake City, UT, USA

关键字：

Private Set Intersection (PSI); Zero-Sharing

摘要：

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.

合写作者：

Yuanchao Luo, Longxin Wang, Xiang Liu, Lin Qi, Wei Wang, Mengmeng Zhou

第一作者：

Ying Gao

论文类型：

会议论文

通讯作者：

Ying Gao

页面范围：

4137–4151

ISSN号：

9798400706363

是否译文：

否

发表时间：

2024-12-09