Paper 2022/713

More Efficient (Reusable) Private Set Union

Abstract

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.