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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.