Authenticated Private Set Intersection: A Merkle Tree-Based Approach for Enhancing Data Integrity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916978261753856 |
|---|---|
| author | Gong, Zixian Zheng, Zhiyong Hu, Zhe Tian, Kun Zhang, Yi Oleksiy, Zhedanov Liu, Fengxia |
| author_facet | Gong, Zixian Zheng, Zhiyong Hu, Zhe Tian, Kun Zhang, Yi Oleksiy, Zhedanov Liu, Fengxia |
| contents | 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 λ+n \log n)$, aligning with the best-known unauthenticated PSI schemes, while the multi-party construction is $\mathcal{O}(n κ+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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_04647 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Authenticated Private Set Intersection: A Merkle Tree-Based Approach for Enhancing Data Integrity Gong, Zixian Zheng, Zhiyong Hu, Zhe Tian, Kun Zhang, Yi Oleksiy, Zhedanov Liu, Fengxia Cryptography and Security 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 λ+n \log n)$, aligning with the best-known unauthenticated PSI schemes, while the multi-party construction is $\mathcal{O}(n κ+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. |
| title | Authenticated Private Set Intersection: A Merkle Tree-Based Approach for Enhancing Data Integrity |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2506.04647 |