1. Malicious Secure Private Set Intersection via Dual Execution 2017 CCS Implementation PSI
    Peter Rindal and Mike Rosulek
    [View PDF on acmccs.github.io]
    [Show BibTex Citation]

    @inproceedings{10.1145/3133956.3134044,
    author = {Rindal, Peter and Rosulek, Mike},
    title = {Malicious-Secure Private Set Intersection via Dual Execution},
    year = {2017},
    isbn = {9781450349468},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    url = {https://doi.org/10.1145/3133956.3134044},
    doi = {10.1145/3133956.3134044},
    booktitle = {Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security},
    pages = {1229–1242},
    numpages = {14},
    keywords = {obliviosu transfer, private set intersection},
    location = {Dallas, Texas, USA},
    series = {CCS ’17}
    }

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 220 requires only 13 seconds with our protocol, which is ~12x faster than the previous best malicious-secure protocol (Rindal & Rosulek, Eurocrypt 2017), and only 3x slower than the best semi-honest protocol (Kolesnikov et al., CCS 2016).

  1.