Welcome to the resource topic for 2021/034
Title:
Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF
Authors: Nishanth Chandran, Divya Gupta, 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.
ePrint: https://eprint.iacr.org/2021/034
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .