Cryptology ePrint Archive: Report 2020/729

Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF

Melissa Chase and Peihan Miao

Abstract: We present a new protocol for two-party private set intersection (PSI) with semi-honest security in the plain model and one-sided malicious security in the random oracle model. Our protocol achieves a better balance between computation and communication than existing PSI protocols. Specifically, our protocol is the fastest in networks with moderate bandwidth (e.g., 30 - 100 Mbps). Considering the monetary cost (proposed by Pinkas et al. in CRYPTO 2019) to run the protocol on a cloud computing service, our protocol also compares favorably.

Underlying our PSI protocol is a new lightweight multi-point oblivious pesudorandom function (OPRF) protocol based on oblivious transfer (OT) extension. We believe this new protocol may be of independent interest.

Category / Keywords: cryptographic protocols / Private Set Intersection, Oblivious Pseudorandom Function, OT Extension, Secure Computation

Original Publication (in the same form): IACR-CRYPTO-2020

Date: received 16 Jun 2020, last revised 11 Aug 2020

Contact author: melissac at microsoft com,peihan@berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20200811:132840 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]