Skip to main navigation Skip to search Skip to main content

Testing disjointness of private datasets

Research output: Contribution to journal › Conference article › peer-review

Abstract

Two parties, say Alice and Bob, possess two sets of elements that belong to a universe of possible values and wish to test whether these sets are disjoint or not. In this paper we consider the above problem in the setting where Alice and Bob wish to disclose no information to each other about their sets beyond the single bit: "whether the intersection is empty or not." This problem has many applications in commercial settings where two mutually distrustful parties wish to decide with minimum possible disclosure whether there is any overlap between their private datasets. We present three protocols that solve the above problem that meet different efficiency and security objectives and data representation scenarios. Our protocols are based on Homomorphic encryption and in our security analysis, we consider the semi-honest setting as well as the malicious setting. Our most efficient construction for a large universe in terms of overall communication complexity uses a new encryption primitive that we introduce called "superposed encryption." We formalize this notion and provide a construction that may be of independent interest. For dealing with the malicious adversarial setting we take advantage of recent efficient constructions of Universally-Composable commitments based on verifiable encryption as well as zero-knowledge proofs of language membership.

Original languageEnglish (US)
Pages (from-to)109-124
Number of pages16
JournalLecture Notes in Computer Science
Volume3570
DOIs
StatePublished - 2005
Event9th International Conference on Financial Cryptography and Data Security, FC 2005 - Roseau, Dominican Republic
Duration: Feb 28 2005 → Mar 3 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Testing disjointness of private datasets'. Together they form a unique fingerprint.

Cite this