Paper 2025/827
Fast Enhanced Private Set Union in the Balanced and Unbalanced Scenarios
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
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
-
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} }