Paper 2017/799

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

Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and Ni Trieu

Abstract

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.