Circuit-PSI With Linear Complexity via Relaxed Batch OPPRF

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.