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)
- 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
-
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}, url = {https://eprint.iacr.org/2017/769} }