Paper 2021/034

Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF

Nishanth Chandran, Divya Gupta, and Akash Shah


In $2$-party Circuit-based Private Set Intersection (Circuit-PSI), $P_0$ and $P_1$ hold sets $\mathsf{S}_{0}$ and $\mathsf{S}_{1}$ respectively and wish to securely compute a function $f$ over the set $\mathsf{S}_{0} \cap \mathsf{S}_{1}$ (e.g., cardinality, sum over associated attributes, or threshold intersection). Following a long line of work, Pinkas et al. ($\mathsf{PSTY}$, Eurocrypt 2019) showed how to construct a concretely efficient Circuit-PSI protocol with linear communication complexity. However, their protocol requires super-linear computation. In this work, we construct concretely efficient Circuit-PSI protocols with linear computational and communication cost. Further, our protocols are more performant than the state-of-the-art, $\mathsf{PSTY}$ -- we are $\approx 2.3\times$ more communication efficient and are up to $2.8\times$ faster. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions ($\mathsf{RBOPPRF}$) that can be seen as a strict generalization of Batch $\mathsf{OPPRF}$s that were used in $\mathsf{PSTY}$. We believe that this primitive could be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.Proceedings on Privacy Enhancing Technologies (PETs), 2022
Private Set IntersectionSecure Computation
Contact author(s)
nichandr @ microsoft com
divya gupta @ microsoft com
t-akshah @ microsoft com
2022-04-06: last of 2 revisions
2021-01-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nishanth Chandran and Divya Gupta and Akash Shah},
      title = {Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF},
      howpublished = {Cryptology ePrint Archive, Paper 2021/034},
      year = {2021},
      doi = {10.2478/popets-2022-0018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.