Paper 2022/653

Fast Unbalanced Private Set Union from Fully Homomorphic Encryption

Binbin Tu, School of Cyber Science and Technology, Shandong University
Yu Chen, School of Cyber Science and Technology, Shandong University
Qi Liu, School of Cyber Science and Technology, Shandong University
Cong Zhang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Private set union (PSU) allows two parties to compute the union of their sets without revealing anything else. It has been widely used in various applications. While several computationally efficient PSU protocols have been developed for the balanced case, they have a potential limitation in their communication complexity, which grows (super)-linearly with the size of the larger set. This poses a challenge when performing PSU in the unbalanced setting, where one party is a constrained device holding a small set, and another is a service provider holding a large set. In this work, we propose a generic construction of unbalanced PSU from leveled fully homomorphic encryption and a newly introduced protocol called permuted matrix private equality test. By instantiating the generic construction, we obtain two unbalanced PSU protocols whose communication complexity is linear in the size of the smaller set, and logarithmic in the larger set. We implement our protocols. Experiments demonstrate that our protocols outperform all previous protocols in the unbalanced setting. The larger difference between the sizes of two sets, the better our protocols perform. For input sets of sizes $2^{10}$ and $2^{20}$ with items of length $128$ bits, our PSU requires only $2.767$ MB of communication. Compared with the state-of-the-art PSU proposed by Zhang et al. (USENIX Security 2023), there are $37 \times$ shrink in communication and roughly $10 - 35 \times$ speedup in the running time depending on the network environments.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2023
unbalanced PSUFHEpermute matrix Private Equality Testpermute and share
Contact author(s)
tubinbin @ mail sdu edu cn
yuchen prc @ gmail com
liuqicst @ mail sdu edu cn
zhangcong @ iie ac cn
2023-08-09: last of 7 revisions
2022-05-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Binbin Tu and Yu Chen and Qi Liu and Cong Zhang},
      title = {Fast Unbalanced Private Set Union from Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/653},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.