Paper 2015/634

Phasing: Private Set Intersection using Permutation-based Hashing

Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner

Abstract

Private Set Intersection (PSI) allows two parties to compute the intersection of private sets while revealing nothing more than the intersection itself. PSI needs to be applied to large data sets in scenarios such as measurement of ad conversion rates, data sharing, or contact discovery. Existing PSI protocols do not scale up well, and therefore some applications use insecure solutions instead. We describe a new approach for designing PSI protocols based on permutation-based hashing, which enables to reduce the length of items mapped to bins while ensuring that no collisions occur. We denote this approach as Phasing, for Permutation-based Hashing Set Intersection. Phasing can dramatically improve the performance of PSI protocols whose overhead depends on the length of the representations of input items. We apply Phasing to design a new approach for circuit-based PSI protocols. The resulting protocol is up to 5 times faster than the previously best Sort-Compare-Shuffle circuit of Huang et al. (NDSS 2012). We also apply Phasing to the OT-based PSI protocol of Pinkas et al. (USENIX Security 2014), which is the fastest PSI protocol to date. Together with additional improvements that reduce the computation complexity by a logarithmic factor, the resulting protocol improves run-time by a factor of up to 20 and can also have similar communication overhead as the previously best PSI protocol in that respect. The new protocol is only moderately less efficient than an insecure PSI protocol that is currently used by real-world applications, and is therefore the first secure PSI protocol that is scalable to the demands and the constraints of current real-world settings.

Note: Added a note on how to achieve correctness when using multiple mapping functions, as was pointed out in http://eprint.iacr.org/2016/665.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. MAJOR revision.USENIX Security Symposium 2015
Contact author(s)
michael zohner @ ec-spride de
History
2016-07-27: last of 2 revisions
2015-06-30: received
See all versions
Short URL
https://ia.cr/2015/634
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/634,
      author = {Benny Pinkas and Thomas Schneider and Gil Segev and Michael Zohner},
      title = {Phasing: Private Set Intersection using Permutation-based Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2015/634},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/634}},
      url = {https://eprint.iacr.org/2015/634}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.