Multi-party private set intersection (PSI) enables multiple parties to compute the common items of private sets without disclosing any other information beyond the result; thus, it has gained significant importance in various distributed computation scenarios. As the number of participants increases, the performance of multi-party PSI protocols is significantly influenced, primarily by the number of interaction rounds needed. In this study, we propose two novel multi-party PSI protocols: the first one is 1MPSI, and the second is 2MPSI. The 1MPSI appears as a wheel structure where the parties need only one round of interactive communication online. 1MPSI is based on the Ring version of Oblivious Linear-function Evaluation (OLE). Benefiting from the wheel structure, 1MPSI supports parallel computation and achieves competitive efficiency between the leader and the other participants (OLE receivers) after input-independent precomputation. The 2MPSI adopts a dual-core star structure and introduces Oblivious Key-Value Store (OKVS), which results in better performance when handling larger set sizes and more participants. Our protocols are designed with simplicity and ease of implementation in mind. Experimental evaluations demonstrate the superiority of our protocols over current open-source multi-party PSI protocols as the set size increases from 2¹² to 2²⁰ when involving 10 and 16 parties. In a test with 16 parties each inputting 2²⁰ elements, 2MPSI achieves a runtime of only 65 seconds.

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 ${}^{\mathrm{ss}}\mathrm{PMT}$ that is based on the secret-sharing private equality test ${}^{\mathrm{ss}}\mathrm{PEQT}$. The ${}^{\mathrm{ss}}\mathrm{PMT}$ 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^{\le }\mathrm{PSI}$) and under-threshold PSI $t^{>}\mathrm{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.