Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF

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 Circuit-PSI 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 (RBOPPRF) that can be seen as a strict generalization of Batch OPPRFs that were used in PSTY. We believe that this primitive could be of independent interest.