Paper 2022/358

Optimal Private Set Union from Multi-Query Reverse Private Membership Test

Cong Zhang
Yu Chen
Weiran Liu
Min Zhang
Dongdai Lin

Private set union (PSU) protocol enables two parties, each holding a set, to compute the union of their sets without revealing anything else to either party. So far, there are two known approaches for constructing PSU protocols. The first mainly depends on additively homomorphic encryption (AHE), which is generally inefficient since it needs to perform a non-constant number of homomorphic computations on each item. The second is mainly based on oblivious transfer and symmetric-key operations, which is recently proposed by Kolesnikov et al. (KRTW, ASIACRYPT 2019). It features good practical performance, which is several orders of magnitude faster than the first one. However, neither of these two approaches is optimal in the sense that their computation and communication complexity are not both $O(n)$, where $n$ is the size of the set. Therefore, the problem of constructing the optimal PSU protocol remains open. In this work, we resolve this open problem by proposing a generic framework of PSU from oblivious transfer and a newly introduced protocol called multi-query reverse private membership test (mq-RPMT). We present two generic constructions of mq-RPMT. The first is based on symmetric-key encryption and general 2PC techniques. The second is based on re-randomizable public-key encryption. Both constructions lead to PSU with linear computation and communication complexity. By instantiating the generic constructions of mq-RPMT, we obtain two concrete PSU protocols based on SKE and PKE techniques respectively. We implement our two PSU protocols and compare them with the state-of-the-art PSU. Experiments show that our PKE-based protocol has the lowest communication of all schemes, which is $3.7-14.8\times$ lower depending on set size. The running time of our PSU scheme is $1.2-12\times$ faster than that of state-of-the-art depending on network environments.

Available format(s)
Cryptographic protocols
Publication info
Contact author(s)
zhangcong @ iie ac cn
yuchen prc @ gmail com
weiran lwr @ alibaba-inc com
zm_min @ mail sdu edu cn
ddlin @ iie ac cn
2022-06-18: revised
2022-03-18: received
See all versions
Short URL
Creative Commons Attribution


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