Welcome to the resource topic for 2025/2019
Title:
Practical Multi-party Private Set Intersection with Reducible Zero-sharing
Authors: Yewei Guan, Hua Guo, Man Ho Au, Jiarong Huo, Jin Tan, Zhenyu Guan
Abstract:Multi-party Private Set Intersection (mPSI) enables n(n\geq3) 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<n) 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\times faster in the LAN setting, 2.69-28.41\times faster in the WAN setting, while the communication cost is 0.29-28.70\times lower. Notably, the total performance (offline+online) still obtains up to 18.73\times improvement. Compared with works with practical efficiency, our mPSI construction achieves similar performance while providing stronger security.
ePrint: https://eprint.iacr.org/2025/2019
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .