Paper 2017/799

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

Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM Conference on Computer and Communications Security (CCS) 2017
Private Set IntersectionOblivious PRFSecure Multiparty ComputationCuckoo Hashing
Contact author(s)
trieun @ oregonstate edu
2017-08-25: received
Short URL
Creative Commons Attribution


      author = {Vladimir Kolesnikov and Naor Matania and Benny Pinkas and Mike Rosulek and Ni Trieu},
      title = {Practical Multi-party Private Set Intersection from Symmetric-Key Techniques},
      howpublished = {Cryptology ePrint Archive, Paper 2017/799},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.