Efficient Three‐Party Private Set Operation With Bilinear Map
Jun Xu, Yu Shang, Shengnan Zhao, Baoyin Sun, Shan Jing, Zhenxiang Chen, Chuan Zhao · Concurrency and Computation Practice and Experience · 2025
ABSTRACT Private set operations (PSO) address key challenges in cross‐organizational data sharing where multiple transport entities securely verify shared cargo manifests or delivery schedules without exposing sensitive information. Private set intersection (PSI) enables secure computation of common elements across private datasets, while its variant, PSI with cardinality (PSI‐CA), reveals only the intersection size. The PSO protocol based on Diffie‐Hellman (DH) key agreement has emerged as a prominent solution for communication‐sensitive applications. However, current research efforts mostly concentrate on two‐party implementations, which face inherent limitations in addressing the communication complexity when scaling to multiple participants. In this work, we firstly present E3PSI‐CA, a novel three‐party PSO protocol. This construction for the semi‐honest model leverages bilinear maps in DH key agreement and Bloom Filters (BF) for compact set representation, achieving remarkable efficiency. By integrating private information retrieval (PIR) techniques, the party in E3PSI‐CAcan efficiently compute the set intersection. To address the inherent accuracy limitations of the BF and extend security to the malicious model, we further propose an enhanced PSI scheme. This variant is built upon a “Ring” structure, within which we employ DH key agreement and OKVS data structure to achieve security against any single malicious party, while the OKVS simultaneously ensures perfect accuracy (zero false positives). We prove the security through the ideal/real simulation paradigm and conduct performance evaluations.