Paper 2019/241
Efficient Circuit-based PSI with Linear Communication
Benny Pinkas, Thomas Schneider, Oleksandr Tkachenko, and Avishay Yanai
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published by the IACR in EUROCRYPT 2019
- Keywords
- Private Set IntersectionSecure Computation
- Contact author(s)
-
benny @ pinkas net
schneider @ encrypto cs tu-darmstadt de
tkachenko @ encrypto cs tu-darmstadt de
ay yanay @ gmail com - History
- 2019-03-13: revised
- 2019-02-28: received
- See all versions
- Short URL
- https://ia.cr/2019/241
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/241,
author = {Benny Pinkas and Thomas Schneider and Oleksandr Tkachenko and Avishay Yanai},
title = {Efficient Circuit-based {PSI} with Linear Communication},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/241},
year = {2019},
url = {https://eprint.iacr.org/2019/241}
}
