## CryptoDB

### Paper: Efficient Circuit-Based PSI with Linear Communication

Authors: Benny Pinkas Thomas Schneider Oleksandr Tkachenko Avishay Yanai DOI: 10.1007/978-3-030-17659-4_5 (login may be required) Search ePrint Search Google We present a new protocol for computing a circuit which implements the private set intersection functionality (PSI). Using circuits for this task is advantageous over the usage of specific protocols for PSI, since many applications of PSI do not need to compute the intersection itself but rather functions based on the items in the intersection.Our protocol is the first circuit-based PSI protocol to achieve linear communication complexity. It is also concretely more efficient than all previous circuit-based PSI protocols. For example, for sets of size $2^{20}$ it improves the communication of the recent work of Pinkas et al. (EUROCRYPT’18) by more than 10 times, and improves the run time by a factor of 2.8x in the LAN setting, and by a factor of 5.8x in the WAN setting.Our protocol is based on the usage of a protocol for computing oblivious programmable pseudo-random functions (OPPRF), and more specifically on our technique to amortize the cost of batching together multiple invocations of OPPRF.
##### BibTeX
@article{eurocrypt-2019-29383,
title={Efficient Circuit-Based PSI with Linear Communication},
booktitle={Advances in Cryptology – EUROCRYPT 2019},
series={Advances in Cryptology – EUROCRYPT 2019},
publisher={Springer},
volume={11478},
pages={122-153},
doi={10.1007/978-3-030-17659-4_5},
author={Benny Pinkas and Thomas Schneider and Oleksandr Tkachenko and Avishay Yanai},
year=2019
}