Paper 2022/358

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

Cong Zhang, Yu Chen, Weiran Liu, Min Zhang, and Dongdai Lin

Abstract

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 $4.1-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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
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
History
2022-03-18: received
Short URL
https://ia.cr/2022/358
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/358,
      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{https://eprint.iacr.org/2022/358}},
      url = {https://eprint.iacr.org/2022/358}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.