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

Multi-party private set intersection (MPSI) allows ( 3) participants, each holding a dataset of size , 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 ( + ).The security of our protocols relies on the assumption * The first two authors contribute equally.