Efficient Circuit-based PSI with Linear Communication

Benny Pinkas; Thomas Schneider; Oleksandr Tkachenko; Avishay Yanai

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 Intersection Secure 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},
      note = {\url{https://eprint.iacr.org/2019/241}},
      url = {https://eprint.iacr.org/2019/241}
}