Paper 2016/746

Improved Private Set Intersection against Malicious Adversaries

Peter Rindal and Mike Rosulek

Abstract

Private set intersection (PSI) refers to a special case of secure two-party computation in which the parties each have a set of items and compute the intersection of these sets without revealing any additional information. In this paper we present improvements to practical PSI providing security in the presence of {\em malicious} adversaries. Our starting point is the protocol of Dong, Chen \& Wen (CCS 2013) that is based on Bloom filters. We identify a bug in their malicious-secure variant and show how to fix it using a cut-and-choose approach that has low overhead while simultaneously avoiding one the main computational bottleneck in their original protocol. We also point out some subtleties that arise when using Bloom filters in malicious-secure cryptographic protocols. We have implemented our PSI protocols and report on its performance. Our improvements reduce the cost of Dong et al.'s protocol by a factor of $14-110\times$ on a single thread. When compared to the previous fastest protocol of De Cristofaro et al., we improve the running time by $8-24\times$. For instance, our protocol has an online time of 14 seconds and an overall time of 2.1 minutes to securely compute the intersection of two sets of 1 million items each.

Note: In this revised version, we add a complete performance comparison with the malicious-secure PSI protocol of De Cristofaro, Kim & Tsudik

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Private Set Intersection
Contact author(s)
rindalp @ oregonstate edu
History
2016-10-03: revised
2016-08-02: received
See all versions
Short URL
https://ia.cr/2016/746
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/746,
      author = {Peter Rindal and Mike Rosulek},
      title = {Improved Private Set Intersection against Malicious Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2016/746},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/746}},
      url = {https://eprint.iacr.org/2016/746}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.