Multi-Party Private Set Intersection With One-Round Online Interaction

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.