Title: Unconditionally secure disjointness tests for private datasets

Authors: Qingsong Ye, Huaxiong Wang, Josef Pieprzyk, Xian-Mo Zhang

Addresses: Centre for Advanced Computing – Algorithms and Cryptography, Department of Computing, Macquarie University, NSW 2109, Australia; Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore. ' Centre for Advanced Computing – Algorithms and Cryptography, Department of Computing, Macquarie University, NSW 2109, Australia; Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore. ' Centre for Advanced Computing – Algorithms and Cryptography, Department of Computing, Macquarie University, NSW 2109, Australia; Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore. ' Centre for Advanced Computing – Algorithms and Cryptography, Department of Computing, Macquarie University, NSW 2109, Australia; Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

Abstract: 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.

Keywords: private matching; private set disjointness; secret sharing; secure multiparty computation; information theoretic security; cryptography; unconditional secure protocols; honest-but-curious; malicious adversaries.

DOI: 10.1504/IJACT.2009.023471

International Journal of Applied Cryptography, 2009 Vol.1 No.3, pp.225 - 235

Available online: 24 Feb 2009 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article