Paper 2021/034

Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF

Nishanth Chandran, Divya Gupta, and Akash Shah

Abstract

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, $$ -- we are $$ more communication efficient and are up to $$ faster. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions ($$) that can be seen as a strict generalization of Batch $$s that were used in $$. We believe that this primitive could be of independent interest.