1. Practical Multi-party Private Set Intersection from Symmteric-Key Techniques 2017 CCS MPC PSI
    Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and Ni Trieu
    [View PDF on acmccs.github.io]
    [Show BibTex Citation]

    @inproceedings{10.1145/3133956.3134065,
    author = {Kolesnikov, Vladimir and Matania, Naor and Pinkas, Benny and Rosulek, Mike and Trieu, Ni},
    title = {Practical Multi-Party Private Set Intersection from Symmetric-Key Techniques},
    year = {2017},
    isbn = {9781450349468},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    url = {https://doi.org/10.1145/3133956.3134065},
    doi = {10.1145/3133956.3134065},
    booktitle = {Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security},
    pages = {1257–1272},
    numpages = {16},
    keywords = {private set intersection, secure multiparty computation, oblivious prf},
    location = {Dallas, Texas, USA},
    series = {CCS ’17}
    }

We present a new paradigm for multi-party private set intersection (PSI) that allows $n$ parties to compute the intersection of their datasets without revealing any additional information. We explore a variety of instantiations of this paradigm. Our protocols avoid computationally expensive public-key operations and are secure in the presence of any number of semi-honest participants (i.e., without an honest majority).

We demonstrate the practicality of our protocols with an implementation. To the best of our knowledge, this is the first implementation of a multi-party PSI protocol. For 5 parties with data-sets of 220 items each, our protocol requires only 72 seconds. In an optimization achieving a slightly weaker variant of security (augmented semi-honest model), the same task requires only 22 seconds.

The technical core of our protocol is oblivious evaluation of a programmable pseudorandom function (OPPRF), which we instantiate in three different ways. We believe our new OPPRF abstraction and constructions may be of independent interest.

  1.