Paper 2022/652

Private Set Operations from Multi-Query Reverse Private Membership Test

Abstract

Private set operations allow two parties to 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 a vector $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 a $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 a $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.

Note: Correct some typos.