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 function (pOPRF). Both cwPRF and pOPRF can be realized from the decisional Diffie-Hellman (DDH) like assumptions in the random oracle model. We also introduce a slightly weak version of mqRPMT dubbed mqRPMT$^*$, in which the client also learns the cardinality of $X \cap Y$. We show that mqRPMT$^*$ can be built 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 PSO protocols that are superior or competitive to the state-of-the-art protocols. For intersection functionality, our protocol is faster than the most efficient one for small sets. For cardinality functionality, our protocol achieves a $2.4-10.5\times$ speedup in running time and a $10.9-14.8\times$ shrinking in communication cost. For cardinality-with-sum functionality, our protocol achieves a $28.5-76.3\times$ speedup in running time and $7.4\times$ shrinking in communication cost. For union functionality, our protocol is the fisrt one that attains strict linear complexity. It requires the least concrete computation and communication costs in all settings, achieving a $2.7-17\times$ speedup in running time and $2\times$ shrinking in communication cost. Concretely, for input set of size $2^{20}$, our PSU protocol requires roughly 100 MB of communication, and 16 seconds using 4 threads on a laptop in the LAN setting. For private-ID functionality, our protocol achieves a $2.7-4.9\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: Add some new materials and update experimental results.