Paper 2022/652

Private Set Operations from Multi-Query Reverse Private Membership Test

Yu Chen, Shandong University, School of Cyber Science and Technology
Min Zhang, Shandong University
Cong Zhang, Chinese Academy of Sciences
Minglang Dong, Shandong University
Weiran Liu, Alibaba Group

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), in which a client with a vector $X = (x_1, \dots, x_n)$ interacts with a server holding a set $Y$, and eventually the server learns only a bit vector $(e_1, \dots, e_n)$ indicating whether $x_i \in Y$ without learning the value of $x_i$, while the client learns nothing. 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 also introduce a slightly weaker 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 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$ shrink in communication cost. For cardinality-with-sum functionality, our protocol achieves a $28.5-76.3\times$ speedup and $7.4\times$ shrink in communication cost. For union functionality, our protocol is the first one that attains strict 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$ shrink in communication cost. Specifically, for input sets 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. Our improvement on PSU also translates to related functionality, yielding the most efficient private-ID protocol to date. 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: Update the experimental results of setting statistical security parameter as 40.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2024
PSOPSUmulti-query RPMTcommutative weak PRFpermuted OPRF
Contact author(s)
yuchen prc @ gmail com
zm_min @ mail sdu edu cn
zhangcong @ iie ac cn
minglang_dong @ mail sdu edu cn
weiran lwr @ alibaba-inc com
2024-02-01: last of 9 revisions
2022-05-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yu Chen and Min Zhang and Cong Zhang and Minglang Dong and Weiran Liu},
      title = {Private Set Operations from Multi-Query Reverse Private Membership Test},
      howpublished = {Cryptology ePrint Archive, Paper 2022/652},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.