Paper 2017/769

Malicious-Secure Private Set Intersection via Dual Execution

Peter Rindal and Mike Rosulek

Abstract

Private set intersection (PSI) allows two parties, who each hold a set of items, to compute the intersection of those sets without revealing anything about other items. Recent advances in PSI have significantly improved its performance for the case of semi-honest security, making semi-honest PSI a practical alternative to insecure methods for computing intersections. However, the semi-honest security model is not always a good fit for real-world problems. In this work, we introduce a new PSI protocol that is secure in the presence of malicious adversaries. Our protocol is based entirely on fast symmetric-key primitives and inherits important techniques from state-of-the-art protocols in the semi-honest setting. Our novel technique to strengthen the protocol for malicious adversaries is inspired by the dual execution technique of Mohassel \& Franklin (PKC 2006). Our protocol is optimized for the random-oracle model, but can also be realized (with a performance penalty) in the standard model. We demonstrate our protocol's practicality with a prototype implementation. To securely compute the intersection of two sets of size $2^{20}$ requires only 13 seconds with our protocol, which is $\sim 12\times$ faster than the previous best malicious-secure protocol (Rindal \& Rosulek, Eurocrypt 2017), and only $3\times$ slower than the best semi-honest protocol (Kolesnikov et al., CCS 2016).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM Conference on Computer and Communications Security (CCS) 2017
Keywords
Private Set Intersection
Contact author(s)
rindalp @ oregonstate edu
History
2017-08-12: received
Short URL
https://ia.cr/2017/769
License
Creative Commons Attribution
CC BY

BibTeX

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