Welcome to the resource topic for 2025/2087
Title:
Leakage-Free Enhanced Private Set Union for Balanced and Unbalanced Scenarios
Authors: Qiang Liu, JaeYoung Bae, JoonWoo Lee
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.
ePrint: https://eprint.iacr.org/2025/2087
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .