Unconditionally secure disjointness tests for private datasets
Summary: We present two unconditional secure protocols for private set disjointness tests. In order to provide intuition of our protocols, we give a naive example that applies Sylvester matrices. Unfortunately, this simple construction is insecure as it reveals information about the intersection cardinality. More specifically, it discloses its lower bound. By using the Lagrange interpolation, we provide a protocol for the honest-but-curious case without revealing any additional information. Finally, we describe a protocol that is secure against malicious adversaries. In this protocol, a verification test is applied to detect misbehaving participants. Both protocols require \(O(1)\) rounds of communication. Our protocols are more efficient than the previous protocols in terms of communication and computation overhead. Unlike previous protocols whose security relies on computational assumptions, our protocols provide information theoretic security. To our knowledge, our protocols are the first ones that have been designed without a generic secure function evaluation. More important, they are the most efficient protocols for private disjointness tests in the malicious adversary case.
- Efficient Disjointness Tests for Private Datasets
- Financial Cryptography and Data Security
- Optimal private halfspace counting via discrepancy
- Privacy-preserving disjunctive normal form operations on distributed sets
- Privacy-preserving data splitting: a combinatorial approach
- Distributed Private Data Analysis
- Unconditional differentially private mechanisms for linear queries
- Verifiable homomorphic oblivious transfer and private equality test
- Universally composable private proximity testing
- Efficient Disjointness Tests for Private Datasets
- Multi Party Distributed Private Matching, Set Disjointness and Cardinality of Set Intersection with Information Theoretic Security
- Financial Cryptography and Data Security
- Applied Cryptography and Network Security
- A communication-efficient private matching scheme in client-server model
This page was built for publication: Unconditionally secure disjointness tests for private datasets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017546)
