Abstract
Private Set Union (PSU) enables two parties to compute the union of their input sets without revealing any additional information. Tu et al. (USENIX Security 2025) introduced the state-of-the-art enhanced PSU (ePSU) framework, which strengthens security by preventing during-execution leakage. However, we observe that directly applying hash-to-bin on input sets within their framework introduces subtle but non-negligible privacy risks. In this work, we address this issue by combining oblivious pseudorandom functions (OPRF) with randomized shuffling, which eliminates the privacy leakage caused by direct hash-to-bin usage. Building on the revised framework, we further optimize the ePSU construction by introducing a bidirectional oblivious key-value store (OKVS), significantly reducing both communication and computational overhead. Experimental results show that, compared with the revised ePSU of Tu et al., our protocol achieves a 1.089–[Formula: see text] reduction in communication cost and a 1.027–[Formula: see text] runtime speedup.