Paper 2025/827

Fast Enhanced Private Set Union in the Balanced and Unbalanced Scenarios

Binbin Tu, School of Cyber Science and Technology, Shandong University
Yujie Bai, School of Cyber Science and Technology, Shandong University
Cong Zhang, Institute for Advanced Study, BNRist, Tsinghua University
Yang Cao, School of Cyber Science and Technology, Shandong University
Yu Chen, School of Cyber Science and Technology, Shandong University
Abstract

Private set union (PSU) allows two parties to compute the union of their sets without revealing anything else. It can be categorized into balanced and unbalanced scenarios depending on the size of the set on both sides. Recently, Jia et al. (USENIX Security 2024) highlight that existing scalable PSU solutions suffer from during-execution leakage and propose a PSU with enhanced security for the balanced setting. However, their protocol's complexity is superlinear with the size of the set. Thus, the problem of constructing a linear enhanced PSU remains open, and no unbalanced enhanced PSU exists. In this work, we address these two open problems: -Balanced case: We propose the first linear enhanced PSU. Compared to the state-of-the-art enhanced PSU (Jia et al., USENIX Security 2024), our protocol achieves a reduction in communication cost and a speedup in running time, depending on set sizes and network environments. -Unbalanced case: We present the first unbalanced enhanced PSU, which achieves sublinear communication complexity in the size of the large set. Experimental results demonstrate that the larger the difference between the two set sizes, the better our protocol performs. For unbalanced set sizes with single thread in Mbps bandwidth, our protocol requires only MB of communication. Compared with the state-of-the-art enhanced PSU, there is shrink in communication and roughly speedup in the running time.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2025
Keywords
Private set unionEnhanced securityBalanced/unbalanced scenariospnMCRGpECRG
Contact author(s)
tubinbin @ sdu edu cn
202217048 @ mail sdu edu cn
zhangcong @ mail tsinghua edu cn
202437063 @ mail sdu edu cn
yuchen @ sdu edu cn
History
2025-05-09: approved
2025-05-09: received
See all versions
Short URL
https://ia.cr/2025/827
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/827,
      author = {Binbin Tu and Yujie Bai and Cong Zhang and Yang Cao and Yu Chen},
      title = {Fast Enhanced Private Set Union in the Balanced and Unbalanced Scenarios},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/827},
      year = {2025},
      url = {https://eprint.iacr.org/2025/827}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.