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
[ Cryptology ePrint archive ]