Lune

USENIX Security2025Top-tier venue

Fast Enhanced Private Set Union in the Balanced and Unbalanced Scenarios

Binbin Tu, Yujie Bai, Cong Zhang, Yang Cao, Yu Chen

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 2.2 -8.8× reduction in communication cost and a 1.2 -8.6× 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 (2 10 , 2 20 ) with single thread in 1Mbps bandwidth, our protocol requires only 2.322 MB of communication. Compared with the state-of-the-art enhanced PSU, there is 38.1× shrink in communication and roughly 17.6× speedup in the running time.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Fast Private Set Intersection from Homomorphic Encryption cites Efficient Batched Oblivious PRF with Applications to Private Set Intersection
  • Labeled PSI from Fully Homomorphic Encryption with Malicious Security cites Fast Private Set Intersection from Homomorphic Encryption
  • Labeled PSI from Fully Homomorphic Encryption with Malicious Security cites Efficient Batched Oblivious PRF with Applications to Private Set Intersection
  • Enhanced Private Set Union from Secret-shared Private Membership Test cites VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Enhanced Private Set Union from Secret-shared Private Membership TestMeng Hao, Guodong Wang, Xinpeng Yang, Pengzhi Xing et al.USENIX Security 2026

Builds on15

  1. Fast Private Set Intersection from Homomorphic EncryptionHao Chen, Kim Laine, Peter RindalCCS 2017 · 446 citations
  2. Efficient Batched Oblivious PRF with Applications to Private Set IntersectionVladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni TrieuCCS 2016 · 429 citations
  3. Labeled PSI from Fully Homomorphic Encryption with Malicious SecurityHao Chen, Zhicong Huang, Kim Laine, Peter RindalCCS 2018 · 242 citations
  4. PSI from PaXoS: Fast, Malicious Private Set IntersectionBenny Pinkas, Mike Rosulek, Ni Trieu, Avishay YanaiEUROCRYPT 2020 · 198 citations
  5. VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLEPeter Rindal, Phillipp SchoppmannEUROCRYPT 2021 · 159 citations

Related papers

  1. Unbalanced Private Set Union with Reduced Computation and CommunicationCong Zhang, Yu Chen, Weiran Liu, Liqiang Peng et al.CCS 2024 · 6 citations
  2. Fast Unbalanced Private Set Union from Fully Homomorphic EncryptionBinbin Tu, Yu Chen, Qi Liu, Cong ZhangCCS 2023 · 11 citations
  3. cwPSU: Efficient Unbalanced Private Set Union via Constant-weight CodesQingwen Li, Song Bian, Hui LiNDSS 2026
  4. Shuffle-based Private Set Union: Faster and More SecureYanxue Jia, Shifeng Sun, Hong-Sheng Zhou, Jiajun Du et al.USENIX Security 2022
  5. Efficient Multi-Party Private Set Union Without Non-Collusion AssumptionsMinglang Dong, Cong Zhang, Yujie Bai, Yu ChenUSENIX Security 2025
Dusk over the sea between two cliffs drawn in fine vertical lines