Efficient and Scalable Circuit-Based Protocol for Multi-party Private Set Intersection

We propose a novel protocol for computing a circuit which implements the multi-party Private Set Intersection (PSI) functionality. The circuit-based approach has advantages over using custom protocols to achieve this task, since many applications of PSI do not require the computation of the intersection itself, but rather specific functional computations over the items in the intersection. As far as we know, our proposal is the first circuit-based multi-party PSI protocol. It generalizes and optimizes the previous two-party sort-compare-shuffle PSI protocol. By designing an efficient multi-party PSI circuit with a succinct output, our protocol demonstrates both high efficiency and good scalability. The resulted protocol has input obliviousness property and achieves a complexity of O(mnlog(mn)) with the uniform size n of sets and the number m of parties. In order to mitigate the overhead associated with circuit-based constructions, we further enhance our protocol by simple hashing and permutation-based hashing. These tricks enable us to minimize circuit size, simultaneously attaining noteworthy reductions in both computation and communication expenses. The optimized protocol does not has input obliviousness property, but achieves an improved complexity of O(mnlog(mlogn)).