Paper 2020/193

PSI from PaXoS: Fast, Malicious Private Set Intersection

Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai


We present a 2-party private set intersection (PSI) protocol which provides security against malicious participants, yet is almost as fast as the fastest known semi-honest PSI protocol of Kolesnikov et al. (CCS 2016). Our protocol is based on a new approach for two-party PSI, which can be instantiated to provide security against either malicious or semi-honest adversaries. The protocol is unique in that the only difference between the semi-honest and malicious versions is an instantiation with different parameters for a linear error-correction code. It is also the first PSI protocol which is concretely efficient while having linear communication and security against malicious adversaries, while running in the OT-hybrid model (assuming a non-programmable random oracle). State of the art semi-honest PSI protocols take advantage of cuckoo hashing, but it has proven a challenge to use cuckoo hashing for malicious security. Our protocol is the first to use cuckoo hashing for malicious-secure PSI. We do so via a new data structure, called a probe-and-XOR of strings (PaXoS), which may be of independent interest. This abstraction captures important properties of previous data structures, most notably garbled Bloom filters. While an encoding by a garbled Bloom filter is larger by a factor of $O(\lambda)$ than the original data, we describe a significantly improved PaXoS based on cuckoo hashing that achieves constant rate while being no worse in other relevant efficiency measures.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
private set intersection
Contact author(s)
ay yanay @ gmail com
benny @ pinkas net
rosulekm @ oregonstate edu
trieun @ oregonstate edu
2020-02-18: received
Short URL
Creative Commons Attribution


      author = {Benny Pinkas and Mike Rosulek and Ni Trieu and Avishay Yanai},
      title = {PSI from PaXoS:  Fast, Malicious Private Set Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2020/193},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.