Two-Party Threshold Private Set Intersection Protocols from Lightweight Cryptographic Primitives

Private Set Intersection (PSI) is a significant application of interest within Secure Multi-party Computation (MPC), even though we are still in the early stages of deploying MPC solutions to real-world problems. Threshold PSI (tPSI), a variant of PSI, allows two parties to determine the intersection of their respective sets only if the cardinality of the intersection is at least (or less than) a specified threshold t. In this paper, we propose a generic construction for two-party tPSI that extensively utilizes Oblivious Transfer (OT). Our approach is based on lightweight primitives and avoids costly public-key systems such as homomorphic encryption. We start by introducing the secret-sharing private membership test PMTss that is based on the secret-sharing private equality test PEQTss. The PMTss enables tPSI to be scaled for a wide range of practical applications, particularly benefiting parties with limited computational resources. Consequently, two distinct two-party tPSI protocols can be efficiently implemented: over-threshold PSI (t≤PSI) and under-threshold PSI t>PSI. In addition, we propose a lightweight two-party tPSI with limited leakage and a generic precomputing OT suitable for phased implementation. Experimental performance demonstrates that our protocols are highly efficient and computationally friendly, thus paving the way for broader deployment of tPSI solutions.