Paper 2014/447

Faster Private Set Intersection based on OT Extension

Benny Pinkas, Thomas Schneider, and Michael Zohner

Abstract

Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI protocols have been proposed. However, the variety of existing PSI protocols makes it difficult to identify the solution that performs best in a respective scenario, especially since they were not all implemented and compared in the same setting. In this work, we give an overview on existing PSI protocols that are secure against semi-honest adversaries. We take advantage of the most recent efficiency improvements in OT extension to propose significant optimizations to previous PSI protocols and to suggest a new PSI protocol whose runtime is superior to that of existing protocols. We compare the performance of the protocols both theoretically and experimentally, by implementing all protocols on the same platform, and give recommendations on which protocol to use in a particular setting.

Note: Added acknowledgement

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. USENIX Security Symposium 2014
Keywords
private set intersectionoblivious transferimplementation
Contact author(s)
michael zohner @ ec-spride de
History
2014-07-28: last of 3 revisions
2014-06-14: received
See all versions
Short URL
https://ia.cr/2014/447
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/447,
      author = {Benny Pinkas and Thomas Schneider and Michael Zohner},
      title = {Faster Private Set Intersection based on OT Extension},
      howpublished = {Cryptology ePrint Archive, Paper 2014/447},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/447}},
      url = {https://eprint.iacr.org/2014/447}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.