Cryptology ePrint Archive: Report 2019/241

Efficient Circuit-based PSI with Linear Communication

Benny Pinkas and Thomas Schneider and 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.

Category / Keywords: cryptographic protocols / Private Set Intersection, Secure Computation

Original Publication (in the same form): IACR-EUROCRYPT-2019

Date: received 27 Feb 2019, last revised 13 Mar 2019

Contact author: benny at pinkas net,schneider@encrypto cs tu-darmstadt de,tkachenko@encrypto cs tu-darmstadt de,ay yanay@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190313:205033 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]