Testing Disjointness of Private Datasets

Antonina Mitrofanova, Aggelos Kiayias

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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
Title of host publicationFinancial Cryptography and Data Security
Subtitle of host publication9th International Conference, FC 2005, Roseau, The Commonwealth of Dominica, February 28 - March 3, 2005, Revised Papers
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-540-31680-0
ISBN (Print)978-3-540-26656-3
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science (LNCS)
Publisher Springer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Testing Disjointness of Private Datasets'. Together they form a unique fingerprint.

Cite this