Practical Multi-Party Private Set Intersection with Reducible Zero-Sharing

Multi-party Private Set Intersection (mPSI) enables $n(n \geq 3)$ parties, each holding a set of size $m$, to jointly compute their intersection while preserving the confidentiality of each set, which is essential for privacy-preserving data analysis and secure database queries. Existing mPSI protocols have limitations in achieving both sufficient security and practical efficiency. This paper presents a novel and efficient mPSI construction in the semi-honest model while resisting arbitrary collusion attacks. Our construction works in the offline/online paradigm. Given the corruption threshold $t$, the online phase achieves linear total computational and communication complexity, that is $O((n+t) m)$, and solely uses symmetric operations. This makes our construction theoretically outperform the existing works. The technical core of the construction is our newly extracted primitive called reducible zero-sharing, which allows $t(t parties to obtain shares of zero for items in the intersection of$n$parties' input set, while resisting up to$t-1$colluding parties. We present a practical construction of reducible zero-sharing in the offline/online paradigm by leveraging the homomorphic property of oblivious key-value store (OKVS). With extensive experiments, we demonstrate that our construction outperforms state-of-the-art works in terms of online running time and communication cost. Specifically, compared to works with sufficient security, the online running time of our mPSI construction is$9.57-114.46 $faster in the LAN setting,$2.69-28.41 $faster in the WAN setting, while the communication cost is$0.29-28.70 $lower. Notably, the total performance (offline+online) still obtains up to$18.73 $ improvement. Compared with works with practical efficiency, our mPSI construction achieves similar performance while providing stronger security.