Private Set Operations from Multi-query Reverse Private Membership Test

Private set operations allow two parties to perform secure computation on their private sets, including intersection, union and functions of intersection/union. In this paper, we put forth a framework to perform private set operations. The technical core of our framework is the multi-query reverse private membership test (mqRPMT) protocol (Zhang et al., USENIX Security 2023). We present two constructions of mqRPMT from newly introduced cryptographic notions, one is based on commutative weak pseudorandom function (cwPRF), and 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 demonstrate the practicality of our framework with implementations. By plugging our cwPRF-based mqRPMT into the 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.5x speedup and a 10.9 - 14.8x reduction in communication cost. For cardinality-with-sum functionality, our protocol achieves a 28.5- 76.3x speedup and 7.4x reduction in communication cost. For union functionality, our protocol is the first one that achieves strictly linear complexity, and requires the lowest concrete computation and communication costs in all settings, achieving a 2.7 - 17x speedup and about 2x reduction in communication cost. Furthermore, our improvement on PSU also translates to related functionality, yielding the most efficient private-ID protocol to date.