[Resource Topic] 2017/799: Practical Multi-party Private Set Intersection from Symmetric-Key Techniques

Welcome to the resource topic for 2017/799

Practical Multi-party Private Set Intersection from Symmetric-Key Techniques

Authors: Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, Ni Trieu


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 2^{20} 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 {\em programmable} pseudorandom function (\OPPRF), which we instantiate in three different ways. We believe our new \OPPRF abstraction and constructions may be of independent interest.

ePrint: https://eprint.iacr.org/2017/799

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .