Cryptology ePrint Archive: Report 2009/491
Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity
Emiliano De Cristofaro and Gene Tsudik
Abstract: Increasing dependence on anytime-anywhere availability of data and the commensurately increasing fear of losing privacy motivate the need for privacy-preserving techniques. One interesting and common problem occurs when two parties need to privately compute an intersection of their respective sets of data. In doing so, one or both parties must obtain the intersection (if one exists), while neither should learn anything about other set. Although prior work has yielded a number of effective and elegant Private Set Intersection (PSI) techniques, the quest for efficiency is still underway. This paper explores some PSI variations and constructs several secure protocols that are appreciably more efficient than the state-of-the-art.
Category / Keywords: cryptographic protocols
Publication Info: Earlier version of this paper appeared in the Proceedings of the International Conference on Financial Cryptography and Data Security 2010.
Date: received 6 Oct 2009, last revised 4 Aug 2010
Contact author: edecrist at uci edu
Available format(s): PDF | BibTeX Citation
Note: Earlier version of this paper appeared in the Proceedings of the International Conference on Financial Cryptography and Data Security 2010.
Version: 20100804:214558 (All versions of this report)
Short URL: ia.cr/2009/491
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]