Paper 2016/930

Scalable 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 compared in the same setting. In addition, existing PSI protocols are several orders of magnitude slower than an insecure naive hashing solution which is used in practice. In this work, we review the progress made on PSI protocols and give an overview of existing protocols in various security models. We then focus on PSI protocols that are secure against semi-honest adversaries and take advantage of the most recent efficiency improvements in OT extension and propose significant optimizations to previous PSI protocols and to suggest a new PSI protocol whose run-time 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, give recommendations on which protocol to use in a particular setting, and evaluate the progress on PSI protocols by comparing them to the currently employed insecure naive hashing protocol. We demonstrate the feasibility of our new PSI protocol by processing two sets with a billion elements each.

Note: This article is an extended and improved version of the conference publications at USENIX Security 2014 and 2015, online at http://eprint.iacr.org/2014/447 and http://eprint.iacr.org/2015/634, respectively. We summarize our contributions over the conference papers in Section 1.4.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. ACM TOPS 2018
DOI
10.1145/3154794
Keywords
oblivious transferprivate set intersection
Contact author(s)
michael zohner @ crisp-da de
History
2019-07-28: revised
2016-09-27: received
See all versions
Short URL
https://ia.cr/2016/930
License
Creative Commons Attribution
CC BY

BibTeX

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