Malicious Private Set Union with Two-Sided Output

Private Set Union (PSU) allows two parties to compute the union of their private sets without revealing any additional information---in particular, it hides their common elements (the intersection). Although recent years have seen significant progress under the semi-honest model, resulting in several efficient two-party PSU protocols, notable gaps remain: (1) some prior works model the semi-honest PSU functionality inaccurately, and (2) practical and scalable maliciously secure protocols are still lacking, except when relying on heavy generic techniques (e.g., FHE, GMW, or general purpose NIZK).

In this paper, we address these issues directly and summarize our contributions as follows:

1. We revisit the formal definition of PSU, covering both the standard one-sided functionality (where only one party receives the output) and the two-sided variant (where both parties receive the output), refuting several flawed claims from prior work, and show that the notion of during-execution leakage'' was not well-defined in the literature, since the enhanced'' functionality is actually equivalent to the standard one.
2. We show how one of the fastest semi-honest protocols can be strengthened against malicious senders with a simple ad-hoc modification, while preserving its efficiency and simplicity.
3. As our main result, we present the first practical, concretely efficient, and maliciously secure two-sided PSU protocol, achieving at least a quadratic improvement over prior work. Along the way, we also resolve the challenge of assuring honest behavior for the hash-to-curve function in the PSU context---a task generally regarded as impractical due to the non-algebraic nature of the hash function.
4. We implement both protocols and compare them with existing schemes. Our experiments demonstrate that our maliciously secure protocols are only ${1.1\!-\!2.4}\times$ slower than the most efficient semi-honest protocols in the literature.