Paper 2020/729

Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF

Melissa Chase and Peihan Miao


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.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2020
Private Set IntersectionOblivious Pseudorandom FunctionOT ExtensionSecure Computation
Contact author(s)
melissac @ microsoft com
peihan @ berkeley edu
2020-08-11: last of 2 revisions
2020-06-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Peihan Miao},
      title = {Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF},
      howpublished = {Cryptology ePrint Archive, Paper 2020/729},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.