International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Private Set Operations from Multi-Query Reverse Private Membership Test

Authors:
Yu Chen , Shandong University
Min Zhang , Shandong University
Cong Zhang , Tsinghua University
Minglang Dong , Shandong University
Weiran Liu , Alibaba Group
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2024
Abstract: 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.5\times$ speedup and a $10.9-14.8\times$ reduction in communication cost. For cardinality-with-sum functionality, our protocol achieves a $28.5-76.3\times$ speedup and $7.4\times$ 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-17\times$ speedup and about $2\times$ reduction in communication cost. Furthermore, our improvement on PSU also translates to related functionality, yielding the most efficient private-ID protocol to date.
BibTeX
@inproceedings{pkc-2024-33757,
  title={Private Set Operations from Multi-Query Reverse Private Membership Test},
  publisher={Springer-Verlag},
  author={Yu Chen and Min Zhang and Cong Zhang and Minglang Dong and Weiran Liu},
  year=2024
}