CryptoDB
PSI from PaXoS: Fast, Malicious Private Set Intersection
| Authors: |
- Benny Pinkas , Bar-Ilan University
- Mike Rosulek , Oregon State University
- Ni Trieu , Oregon State University
- Avishay Yanai , VMware Research, Israel
|
| Download: |
- DOI: 10.1007/978-3-030-45724-2_25
(login may be required)
- Search ePrint
- Search Google
|
| Presentation: |
Slides
|
|
Conference:
|
EUROCRYPT 2020
|
| Abstract: |
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 $\Omega(\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. |
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30235,
title={PSI from PaXoS: Fast, Malicious Private Set Intersection},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={Private set intersection;PSI;secure multi-party computation;MPC;oblivious transfer;OT.},
volume={12105},
doi={10.1007/978-3-030-45724-2_25},
author={Benny Pinkas and Mike Rosulek and Ni Trieu and Avishay Yanai},
year=2020
}
