Cryptology ePrint Archive: Report 2017/799

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

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

Category / Keywords: cryptographic protocols / Private Set Intersection; Oblivious PRF; Secure Multiparty Computation; Cuckoo Hashing

Original Publication (in the same form): ACM Conference on Computer and Communications Security (CCS) 2017

Date: received 24 Aug 2017

Contact author: trieun at oregonstate edu

Available format(s): PDF | BibTeX Citation

Version: 20170825:191304 (All versions of this report)

Short URL: ia.cr/2017/799