O-Ring and K-Star: Efficient Multi-party Private Set Intersection

Multi-party private set intersection (mPSI) securely enables multiple parties to know the intersection of their sets without disclosing anything else. Many mPSI protocols are not efficient in practice. In this paper, we propose two efficient mPSI protocols that are secure against an arbitrary number of colluding parties. In the protocol O-Ring, we take advantage of the ring network topology such that the communication costs of the party with the largest workload can be cheaper than other mPSI protocols with a star topology. In the protocol K-Star, we take advantage of the star topology to support better concurrency such that the protocol can run fast. K-Star is suitable for applications with a powerful centralized server. Different from KMPRT (CCS'17) and CDGOSS (CCS'21) that rely on Oblivious Programmable PRF primitive, we simply utilize the cheaper Oblivious PRF (OPRF) and a data structure Oblivious Key-value Store (OKVS). We further propose two fine-grained optimizations for OKVS and OPRF in multi-party cases to improve runtime performance.

After extensive experiments, we demonstrate that both protocols run the fastest and achieve the lowest total communication costs compared with the state-of-the-art counterparts in most settings. Specifically, O-Ring/K-Star is respectively 1.6 × ∼ 48.3 × 1.6×∼48.3× and 4.0 × ∼ 39.8 × 4.0×∼39.8× (except one setting) cheaper than KMPRT (CCS'17) and CDGOSS (CCS'21) in the total communication costs. For the total running time, K-Star can be respectively 1.4 × ∼ 9.0 × 1.4×∼9.0× and 1.0 × ∼ 15.3 × 1.0×∼15.3× as fast as them in the LAN setting.