Paper 2025/2087

Leakage-Free Enhanced Private Set Union for Balanced and Unbalanced Scenarios

Abstract

Private Set Union (PSU) enables two parties to compute the union of their input sets without revealing anything else. Depending on set sizes, PSU is studied in balanced and unbalanced settings. Tu et al. (USENIX Security 2025) presented state-of-the-art enhanced PSU (ePSU) protocols under a unified framework in both settings, achieving enhanced security by preventing during-execution leakage. However, we observe that directly applying hash-to-bin on input sets within their framework introduces potential privacy risks. Moreover, the communication of their unbalanced ePSU still scales with the larger set size, rather than being linear in only the smaller set size. In this work, we address these open problems. We employ a combination of oblivious pseudorandom function (OPRF) and shuffling to mitigate the potential privacy leakage that arises when directly applying the hash-to-bin within the framework of Tu et al. (USENIX Security 2025). Building upon this, we further optimize their balanced ePSU protocol by leveraging a bidirectional oblivious key-value store (OKVS). Compared with the corrected version of Tu et al.'s balanced ePSU, ours achieves a $1.1-3.0\times$ shrinking in communication and a $1.2-1.6\times$ speedup in runtime. We design the first unbalanced ePSU whose communication is linear solely in the smaller set size. Since no hash-to-bin is used, it is inherently free from the associated privacy leakage. With the smaller set size fixed at $2^{10}$, ours reduces communication by $1.5-45.8\times$ compared with corrected version of Tu et al.'s unbalanced ePSU, while achieving $1.3-6.7\times$ runtime speedups.