@inproceedings{chandran2022circuit-psi,
author = {Chandran, Nishanth and Gupta, Divya and Shah, Akash},
title = {Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF},
booktitle = {22nd Privacy Enhancing Technologies Symposium (PETS 2022)},
year = {2022},
month = {June},
abstract = {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.},
url = {http://approjects.co.za/?big=en-us/research/publication/circuit-psi-with-linear-complexity-via-relaxed-batch-opprf/},
}