Paper 2024/922

Scalable Private Set Union, with Stronger Security

Yanxue Jia, Purdue University West Lafayette
Shi-Feng Sun, Shanghai Jiao Tong University
Hong-Sheng Zhou, Virginia Commonwealth University
Dawu Gu, Shanghai Jiao Tong University

Private Set Union (PSU) protocol allows parties, each holding an input set, to jointly compute the union of the sets without revealing anything else. In the literature, scalable PSU protocols follow the “split-execute-assemble” paradigm (Kolesnikov et al., ASIACRYPT 2019); in addition, those fast protocols often use Oblivious Transfer as building blocks. Kolesnikov et al. (ASIACRYPT 2019) and Jia et al. (USENIX Security 2022), pointed out that certain security issues can be introduced in the “split-execute-assemble” paradigm. In this work, surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage, and only the PSU protocols based on additively homomorphic encryption (AHE) can avoid the leakage. However, the AHE-based PSU protocols are far from being practical. To bridge the gap, we also design a new PSU protocol that can avoid the unnecessary leakage. Unlike the AHE-based PSU protocols, our new construction only relies on symmetric-key operations other than base OTs, thereby being much more scalable. The experimental results demonstrate that our protocol can obtain at least 873.74× speedup over the best-performing AHE-based scheme. Moreover, our performance is comparable to that of the state-of-the-art PSU protocol (Chen et al., USENIX Security 2023), which also suffers from the unnecessary leakage.

Note: This replaces an earlier version at; Compared with, this work added a new construction.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2024
Private Set UnionLeakage
Contact author(s)
jia168 @ purdue edu
shifeng sun @ sjtu edu cn
hszhou @ vcu edu
dwgu @ sjtu edu cn
2024-06-13: last of 2 revisions
2024-06-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yanxue Jia and Shi-Feng Sun and Hong-Sheng Zhou and Dawu Gu},
      title = {Scalable Private Set Union, with Stronger Security},
      howpublished = {Cryptology ePrint Archive, Paper 2024/922},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.