Authenticated Private Set Intersection: A Merkle Tree-Based Approach for Enhancing Data Integrity
By: Zixian Gong , Zhiyong Zheng , Zhe Hu and more
Potential Business Impact:
Protects secret lists from cheating during sharing.
Private Set Intersection (PSI) enables secure computation of set intersections while preserving participant privacy, standard PSI existing protocols remain vulnerable to data integrity attacks allowing malicious participants to extract additional intersection information or mislead other parties. In this paper, we propose the definition of data integrity in PSI and construct two authenticated PSI schemes by integrating Merkle Trees with state-of-the-art two-party volePSI and multi-party mPSI protocols. The resulting two-party authenticated PSI achieves communication complexity $\mathcal{O}(n \lambda+n \log n)$, aligning with the best-known unauthenticated PSI schemes, while the multi-party construction is $\mathcal{O}(n \kappa+n \log n)$ which introduces additional overhead due to Merkle tree inclusion proofs. Due to the incorporation of integrity verification, our authenticated schemes incur higher costs compared to state-of-the-art unauthenticated schemes. We also provide efficient implementations of our protocols and discuss potential improvements, including alternative authentication blocks.
Similar Papers
Communication Efficient Multiparty Private Set Intersection from Multi-Point Sequential OPRF
Cryptography and Security
Lets groups find shared secrets safely.
Multi-Party Private Set Operations from Predicative Zero-Sharing
Cryptography and Security
Lets groups secretly combine their private lists.
Multi-Agent Distributed Optimization With Feasible Set Privacy
Information Theory
Helps agents find best answer without sharing secrets.