Circuit-PSI With Linear Complexity via Relaxed Batch OPPRF
Authors: Nishanth Chandran (Microsoft Research.), Divya Gupta (Microsoft Research.), Akash Shah (UCLA. Work done at Microsoft Research.)
Volume: 2022
Issue: 1
Pages: 353–372
DOI: https://doi.org/10.2478/popets-2022-0018
Abstract: In 2-party Circuit-based Private Set Intersection (Circuit-PSI), P0 and P1 hold sets S0 and S1 respectively and wish to securely compute a function f over the set S0 ∩ S1 (e.g., cardinality, sum over associated attributes, or threshold intersection). Following a long line of work, Pinkas et al. (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 CircuitPSI protocols with linear computational and communication cost. Further, our protocols are more performant than the state-of-the-art, PSTY – we are ≈ 2.3× more communication efficient and are up to 2.8× faster. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions (RB-OPPRF) that can be seen as a strict generalization of Batch OPPRFs that were used in PSTY. This primitive could be of independent interest.
Keywords: Private Set Intersection (PSI), Circuit-PSI, Secure Two Party Computation.
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
