Cryptology ePrint Archive: Report 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).

Category / Keywords: cryptographic protocols / Private Set Intersection

Original Publication (with minor differences): ACM Conference on Computer and Communications Security (CCS) 2017

Date: received 9 Aug 2017

Contact author: rindalp at oregonstate edu

Available format(s): PDF | BibTeX Citation

Version: 20170812:072921 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]