Malicious-Secure Private Set Intersection via Dual Execution

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\u27s 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)