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 a four-round protocol and two-round protocol, each with two variants. Our four-round protocol focusing on runtime out-performs the state-of-the-art in runtime for the majority of the medium bandwidth settings ($100$Mbps) and the large set size ($\geq 2^{20}$) settings, with a runtime that is 1.04X-1.25X faster than existing protocols. Our other four-round variant focusing on communication outperforms the state-of-the-art in communication by up to a factor of 1.43 when the set size $\geq 2^{18}$. On the other hand, our two-round protocol is only slightly more expensive but has the property that the receiver message can be re-used across multiple executions. All our semi-honest protocols are post-quantum secure if post-quantum primitives (OKVS and OT) are used. In the setting where the sender is malicious, we provide the first protocols that avoid using expensive zero-knowledge proofs. Our four-round protocol costs less than double in both communication and computation compared to all other semi-honest constructions, showcasing great efficiency. As in the semi-honest setting, we also give a 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 private set union.

Available format(s)
Cryptographic protocols
Publication info
Private Set UnionSecure Two-Party ComputationReusability
Contact author(s)
gordon @ gmu edu
carmit hazay @ biu ac il
ple13 @ gmu edu
mliang5 @ gmu edu
2024-02-04: last of 2 revisions
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.