Paper 2022/713

More Efficient (Reusable) Private Set Union

Dov Gordon, George Mason University
Carmit Hazay, Bar-Ilan University
Phi Hung Le, George Mason University
Mingyu Liang, George Mason University

We study the problem of private set union in the two-party setting, providing several new constructions. We consider the case where one party is designated to receive output. In the semi-honest setting, we provide two protocols. Our four-round protocol out-performs the state-ofthe-art in both communication and computation, and has a runtime that is 1.3X-2X faster than existing protocols. Our two-round protocol is only slightly more expensive, but it is still faster than existing protocols and has the property that the receiver message can be re-used across multiple executions. All our semi-honest protocols are post-quantum secure. In the setting where the sender is malicious, we provide the first protocols that avoid the use of expensive zero-knowledge proofs. We estimate (conservatively) that our constructions are less than 2X more expensive than the best known semi-honest constructions. As in the semi-honest setting, we describe two protocols: a faster one that requires four rounds of communication, and a slightly more expensive protocol that allows the receiver message to be re-used. Our work draws on several techniques from the literature on private set intersection, and helps clarify how these techniques generalize (and don’t generalize) to the problem of PSU.

Available format(s)
Cryptographic protocols
Publication info
Private Set Union Secure Two-Party Computation Reusability
Contact author(s)
gordon @ gmu edu
carmit hazay @ biu ac il
ple13 @ gmu edu
mliang5 @ gmu edu
2022-06-06: revised
2022-06-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dov Gordon and Carmit Hazay and Phi Hung Le and Mingyu Liang},
      title = {More Efficient (Reusable) Private Set Union},
      howpublished = {Cryptology ePrint Archive, Paper 2022/713},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.