Towards an improved efficient leakage-resilient enhanced private set union

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–$$3.049\times$$ reduction in communication cost and a 1.027–$$1.744\times$$ runtime speedup.