EoTMP: Efficient Over-Threshold Multi-Party Private Set Intersection

Over-Threshold Multi-Party Private Set Intersection (OT-MPSI) is a variant of MPSI that aims to return items that appear in at least T of participants’ sets without revealing any other information. OT-MPSI is applicable to many practical scenarios and offers an advantage over MPSI when identifying items held by most but not all participants. The existing work processes binary vector representations of sets in a bit-wise manner and utilizes Secure Computation Protocols to achieve over-threshold functionality. This results in low computational efficiency, with the number of communication rounds scaling linearly with the number of participants. We propose an efficient OT-MPSI protocol (EoTMP) by utilizing ring learning with errors based multi-party homomorphic encryption. By introducing a new over-threshold functionality and leveraging additional optimization techniques, our EoTMP requirs only three communication rounds and offers faster computation than the state-of-the-art. In addition, our scheme supports the t-N threshold access-structure for participant collaboration. Specially, with 45 participants and a threshold of 40, EoTMP processes sets of size 256 in 0.6 seconds, achieving a reduction in computational overhead by three orders of magnitude compared to prior work.