Welcome to the resource topic for 2022/652
Title:
Private Set Operations from Multi-Query Reverse Private Membership Test
Authors: Yu Chen, Min Zhang, Cong Zhang, and Minglang Dong
Abstract:Private set operations allow two parties perform secure computation on two private sets, such as intersection or union related functions. In this paper, we identify a framework for performing private set operations. At the technical core of our framework is multi-query reverse private membership test (mqRPMT), which is a natural extension of RPMT recently proposed by Kolesnikov et al.~\cite{KRTW-ASIACRYPT-2019}. In mqRPMT, a client with set X = (x_1, \dots, x_n) interacts with a server holding a set Y. As a result, the server only learns a bit vector (e_1, \dots, e_n) indicating whether x_i \in Y but without knowing the value of x_i, while the client learns nothing. We present two constructions of mqRPMT from newly introduced cryptographic primitive and protocol. One is based on commutative weak pseudorandom function (cwPRF), the other is based on permuted oblivious pseudorandom functions (pOPRF). Both cwPRF and pOPRF can be instantiated from the decisional Diffie-Hellman like assumptions in the random oracle model. We also introduce a slight weak version of mqRPMT dubbed mqRPMT$^$, in which the client learns the cardinality of X \cap Y. We show mqRPMT$^$ can be build from a category of multi-query private membership test (mqPMT) called Sigma-mqPMT, which in turn can be realized from DDH-like assumptions or oblivious polynomial evaluation. This makes the first step towards establishing the relation between mqPMT and mqRPMT. We demonstrate the practicality of our framework with implementations. By plugging our cwPRF-based mqRPMT to the general framework, we obtain various efficient PSO protocols that are competitive or superior to the-state-of-art protocols. For cardinality functionality, our protocol achieves a 1.17-6.62\times speedup in running time and 10.85-14.80\times shrinking in communication cost. For cardinality-with-sum functionality, our protocol achieves a 8-40\times speedup in running time and 10 \times shrinking in communication cost. For union functionality, our protocol achieves strict linear complexity. Among all the existing PSU protocols, it requires the least concrete communication cost, and is also the fastest one in the WAN setting. Specifically, for input set of size 2^{20}, our PSU protocol requires roughly 100 MB bandwidth, and 58 seconds using 4 threads in the LAN setting. For private-ID functionality, our protocol achieves a 1.39-4.75\times speedup in running time. Moreover, by plugging our FHE-based mqRPMT$^ to the general framework, we obtain a PSU^$ protocol (the sender additionally learns the intersection size) suitable for unbalanced setting, whose communication complexity is linear in the size of the smaller set, and logarithmic in the larger set.
ePrint: https://eprint.iacr.org/2022/652
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 .