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, $\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)
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.Proceedings on Privacy Enhancing Technologies (PETs), 2022
DOI
10.2478/popets-2022-0018
Keywords
Private Set IntersectionSecure Computation
Contact author(s)
nichandr @ microsoft com
divya gupta @ microsoft com
t-akshah @ microsoft com
History
2022-04-06: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/034

CC BY

BibTeX

@misc{cryptoeprint:2021/034,
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{https://eprint.iacr.org/2021/034}},
url = {https://eprint.iacr.org/2021/034}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.