Efficient disjointness tests for private datasets

Qingsong Ye*, Huaxiong Wang, Josef Pieprzyk, Xian Mo Zhang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

8 Citations (Scopus)


We present efficient protocols for private set disjointness tests. We start from an intuition of our protocols that applies Sylvester matrices. Unfortunately, this simple construction is insecure as it reveals information about the cardinality of the intersection. 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. The protocol applies a verification test 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 first ones that have been designed without a generic secure function evaluation. More importantly, they are the most efficient protocols for private disjointness tests for the malicious adversary case.

Original languageEnglish
Title of host publicationInformation Security and Privacy
Subtitle of host publication13th Australasian Conference, ACISP 2008, Wollongong, Australia, July 7-9, 2008. Proceedings
EditorsYi Mu, Willy Susilo, Jennifer Seberry
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Number of pages15
ISBN (Electronic)9783540705000
ISBN (Print)9783540699712
Publication statusPublished - 2008
Event13th Australasian Conference on Information Security and Privacy, ACISP 2008 - Wollongong, NSW, Australia
Duration: 7 Jul 20089 Jul 2008

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th Australasian Conference on Information Security and Privacy, ACISP 2008
CityWollongong, NSW


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

Cite this