Paper 2022/750

The Ideal Functionalities for Private Set Union, Revisited

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

A 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, when we design scalable two-party PSU protocols, we follow the so-called ``split-execute-assemble'' paradigm, and also use Oblivious Transfer as a building block. Recently, Kolesnikov et al. (ASIACRYPT 2019) pointed out that security issues could be introduced when we design PSU protocols following the ``split-execute-assemble'' paradigm. Surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage. In this work, to enable a better understanding of the security for PSU, we provide a systematic treatment of the typical PSU protocols, which may shed light on the design of practical and secure PSU protocols in the future. More specifically, we define different versions of PSU functionalities to properly capture the subtle security issues arising from protocols following the ``split-execute-assemble'' paradigm and using Oblivious Transfer as subroutines. Then, we survey the typical PSU protocols, and categorize these protocols into three design frameworks, and prove what PSU functionality the protocols under each framework can achieve at best, in the semi-honest setting.

Available format(s)
Cryptographic protocols
Publication info
Contact author(s)
jiayanxue @ sjtu edu cn
shifeng sun @ sjtu edu cn
hszhou @ vcu edu
dwgu @ sjtu edu cn
2022-06-14: approved
2022-06-13: received
See all versions
Short URL
No rights reserved


      author = {Yanxue Jia and Shi-Feng Sun and Hong-Sheng Zhou and Dawu Gu},
      title = {The Ideal Functionalities for Private Set Union, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2022/750},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.