**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.

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

**Date: **received 9 Jan 2021

**Contact author: **nichandr at microsoft com,divya gupta@microsoft com,t-akshah@microsoft com

**Available format(s): **PDF | BibTeX Citation

**Version: **20210112:075748 (All versions of this report)

**Short URL: **ia.cr/2021/034

[ Cryptology ePrint archive ]