t-PSI: Efficient Multi-party Private Set Intersection with Threshold

Multi-party privacy set intersection (MPSI) enables multiple parties to compute the intersection of their datasets without leaking data privacy. Among existing MPSI protocols, e.g., KMPRT-based protocols, oblivious evaluation of programmable pseudo-random function (OPPRF) or oblivious pseudo-random function (OPRF) is typically used to generate pseudo random numbers, requiring frequent online interactions. To mitigate such communication overheads, we propose the threshold Privacy Set Intersection (t-PSI) protocol for multi-party, leveraging the Shamir Secret Sharing (SSS) protocol and the masking construction mechanism. We propose two types of masking construction mechanisms: Polynomial and Garbled Bloom-filter. To the best of our knowledge, this is the first Secret Sharing-based MPSI protocol. With the significant reduction of inter-party communication, the t-PSI protocol is highly scalable and can handle datasets ranging from 26 to 220. Further, with built-in fault tolerance, t-PSI works even if some parties went offline during protocol execution. As shown in the experiments, for five parties with datasets of 220 items each, the proposed t-PSI takes only 63 seconds, outperforming the state-of-the-art in [1].