Paper 2022/157

Shuffle-based Private Set Union: Faster and More Secure

Yanxue Jia, Shi-Feng Sun, Hong-Sheng Zhou, Jiajun Du, and Dawu Gu


Private Set Union ($\mathsf{PSU}$) allows two players, the sender and the receiver, to compute the union of their input datasets without revealing any more information than the result. While it has found numerous applications in practice, not much research has been carried out so far, especially for large datasets. In this work, we take shuffling technique as a key to design $\mathsf{PSU}$ protocols for the first time. By shuffling receiver's set, we put forward the first protocol, denoted as $\Pi_{\mathsf{PSU}}^{\mathsf{receiver}}$, that eliminates the expensive operations in previous works, such as additive homomorphic encryption and repeated operations on the receiver's set. It outperforms the state-of-the-art design by Kolesnikov et al. (ASIACRYPT 2019) in both efficiency and security; the unnecessary leakage in Kolesnikov et al.'s design, can be avoided in our design. We further extend our investigation to the application scenarios in which both players may hold unbalanced input datasets. We propose our second protocol $\Pi_{\mathsf{PSU}}^{\mathsf{sender}}$, by shuffling the sender's dataset. This design can be viewed as a dual version of our first protocol, and it is suitable in the cases where the sender's input size is much smaller than the receiver's. Finally, we implement our protocols $\Pi_{\mathsf{PSU}}^{\mathsf{receiver}}$ and $\Pi_{\mathsf{PSU}}^{\mathsf{sender}}$ in C++ on big datasets, and perform a comprehensive evaluation in terms of both scalability and parallelizability. The results demonstrate that our design can obtain a $4$-$5 \times$ improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2022
two-party computationprivate set union
Contact author(s)
jiayanxue @ sjtu edu cn
2022-02-24: last of 3 revisions
2022-02-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yanxue Jia and Shi-Feng Sun and Hong-Sheng Zhou and Jiajun Du and Dawu Gu},
      title = {Shuffle-based Private Set Union: Faster and More Secure},
      howpublished = {Cryptology ePrint Archive, Paper 2022/157},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.