Paper 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.

Note: Earlier version of this paper appeared in the Proceedings of the International Conference on Financial Cryptography and Data Security 2010.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Earlier version of this paper appeared in the Proceedings of the International Conference on Financial Cryptography and Data Security 2010.
Keywords
cryptographic protocols
Contact author(s)
edecrist @ uci edu
History
2010-08-04: last of 6 revisions
2009-10-14: received
See all versions
Short URL
https://ia.cr/2009/491
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/491,
      author = {Emiliano De Cristofaro and Gene Tsudik},
      title = {Practical Private Set Intersection Protocols with  Linear Computational and Bandwidth Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2009/491},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/491}},
      url = {https://eprint.iacr.org/2009/491}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.