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 found numerous applications in practice. Recently, some computationally efficient PSU protocols have been designed for the balanced case, but a limitation with these protocols is the communication complexity, which scales (super)-linear in the size of the larger set. This is of particular concern when performing PSU in the unbalanced case, where one party is a constrained device holding a small set, and another is a large 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 secure and fast 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 and compare them with the state-of-the-art PSU. Experiments show that our protocols are more efficient than all previous protocols in the unbalanced case. Especially, the larger difference between the size of two sets, the better our protocols perform. For input sets of size $2^{10}$ and $2^{20}$ with 128-bit length items, our PSU takes $2.767$ MB of communication to compute the union. Compared with the state-of-the-art PSU proposed by Zhang et al. (Usenix Security 2023), there are $37 \times$ reductions in communication and roughly $10 - 35 \times$ reductions in computational overhead depending on network environments.

Available format(s)
Cryptographic protocols
Publication info
unbalanced PSU FHE permute matrix Private Equality Test permute and share
Contact author(s)
tubinbin @ mail sdu edu cn
yuchen @ sdu edu cn
liuqicst @ mail sdu edu cn
zhangcong @ iie ac cn
2022-11-03: last of 4 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.