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.
Category / Keywords: cryptographic protocols / Private Set Intersection, Secure Computation Date: received 9 Jan 2021, last revised 25 Feb 2021 Contact author: nichandr at microsoft com,divya gupta@microsoft com,t-akshah@microsoft com Available format(s): PDF | BibTeX Citation Version: 20210225:101051 (All versions of this report) Short URL: ia.cr/2021/034