Authenticated Private Set Intersection: A Merkle Tree-Based Approach for Enhancing Data Integrity

• URL: http://arxiv.org/abs/2506.04647v1
• Date: Thu, 05 Jun 2025 05:28:59 GMT
• Title: Authenticated Private Set Intersection: A Merkle Tree-Based Approach for Enhancing Data Integrity
• Authors: Zixian Gong, Zhiyong Zheng, Zhe Hu, Kun Tian, Yi Zhang, Zhedanov Oleksiy, Fengxia Liu,
• Abstract summary: Private Set Intersection (PSI) enables secure computation of set intersections while preserving participant privacy.<n>Standard PSI existing protocols remain vulnerable to data integrity attacks allowing malicious participants to extract additional intersection information.<n>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.
• Score: 12.57031390693896
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• IDCloak: A Practical Secure Multi-party Dataset Join Framework for Vertical Privacy-preserving Machine Learning [7.765213701941396]
  This paper proposes IDCloak, the first practical secure multi-party dataset join framework for vPPML.<n>We show that IDCloak demonstrates higher efficiency in the two-party setting and comparable performance when the party number increases.<n>Our proposed cmPSI protocol provides a stronger security guarantee (dishonest majority) while improving efficiency by up to $7.78times$ in time and $8.73times$ in communication sizes.
  arXiv  Detail & Related papers  (2025-06-01T16:20:39Z)
• FedRE: Robust and Effective Federated Learning with Privacy Preference [20.969342596181246]
  Federated Learning (FL) employs gradient aggregation at the server for distributed training to prevent the privacy leakage of raw data.<n>Private information can still be divulged through the analysis of uploaded gradients from clients.<n>Existing methods fail to take practical issues into account by merely perturbing each sample with the same mechanism.
  arXiv  Detail & Related papers  (2025-05-08T01:50:27Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• AnonPSI: An Anonymity Assessment Framework for PSI [5.301888664281537]
  Private Set Intersection (PSI) is a protocol that enables two parties to securely compute a function over the intersected part of their shared datasets. Recent studies have highlighted its vulnerability to Set Membership Inference Attacks (SMIA) This paper explores the evaluation of anonymity within the PSI context.
  arXiv  Detail & Related papers  (2023-11-29T22:13:53Z)
• Secure and Scalable Circuit-based Protocol for Multi-Party Private Set Intersection [4.946124980718068]
  Circuit-based approach has advantages over using custom protocols to achieve this task. By using secure computation between two parties, our protocol sidesteps the complexities associated with multi-party interactions. In order to mitigate the high overhead associated with circuit-based constructions, we have further enhanced our protocol by utilizing simple hashing scheme and permutation-based hash functions.
  arXiv  Detail & Related papers  (2023-09-14T03:20:33Z)
• Advancement on Security Applications of Private Intersection Sum Protocol [1.0485739694839666]
  Secure computation protocols combine inputs from involved parties to generate an output while keeping their inputs private. Private Set Intersection (PSI) is a secure computation protocol that allows two parties to learn the intersection of their sets without revealing anything else. Private Intersection Sum (PIS) extends PSI when the two parties want to learn the cardinality of the intersection. Private Join and Compute (PJC) is a scalable extension of PIS protocol to help organizations work together with confidential data sets.
  arXiv  Detail & Related papers  (2023-08-28T17:42:53Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Differentially Private Federated Clustering over Non-IID Data [59.611244450530315]
  clustering clusters (FedC) problem aims to accurately partition unlabeled data samples distributed over massive clients into finite clients under the orchestration of a server. We propose a novel FedC algorithm using differential privacy convergence technique, referred to as DP-Fed, in which partial participation and multiple clients are also considered. Various attributes of the proposed DP-Fed are obtained through theoretical analyses of privacy protection, especially for the case of non-identically and independently distributed (non-i.i.d.) data.
  arXiv  Detail & Related papers  (2023-01-03T05:38:43Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.