Paper 2021/034

Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF

Nishanth Chandran and Divya Gupta and Akash Shah

Abstract

In a two-party Circuit-based Private Set Intersection (PSI), $P_{0}$ and $P_{1}$ hold sets $X$ and $Y$ respectively and wish to securely compute a function $f$ over the set $X \cap Y$ (e.g., cardinality, sum over associated attributes, and threshold intersection). Following a long line of work, Pinkas et al. ($\mathsf{PSTY}$, Eurocrypt 2019) showed how to construct such a Circuit-PSI protocol with linear communication complexity. However, their protocol has super-linear computational complexity. In this work, we construct Circuit-PSI protocols with linear computational and communication cost. Further, our protocols are concretely more efficient than $\mathsf{PSTY}$ -- we are $\approx 2.3\times$ more communication efficient and are up to $2.8\times$ faster in LAN and WAN network settings. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions ($\mathsf{RB\text{-}OPPRF}$) that can be seen as a strict generalization of Batch $\mathsf{OPPRF}$s in $\mathsf{PSTY}$. While using Batch $\mathsf{OPPRF}$s, in the context of Circuit-PSI results, in protocols with super-linear computational complexity, we construct $\mathsf{RB\text{-}OPPRF}$s that can be used to build linear cost and concretely efficient Circuit-PSI protocols. We believe that the $\mathsf{RB\text{-}OPPRF}$ primitive could be of independent interest. As another contribution, we provide more communication efficient protocols (than prior works) for the task of private set membership -- a primitive used in many PSI protocols including ours.