Enhanced Private Set Union from Secret-shared Private Membership Test

Meng Hao, Singapore Management University; Guodong Wang, University of Electronic Science and Technology of China; Xinpeng Yang, Nanyang Technological University; Pengzhi Xing and Hanxiao Chen, University of Electronic Science and Technology of China; Tianwei Zhang, Nanyang Technological University; Haiyang Xue and Guomin Yang, Singapore Management University; Hongwei Li, University of Electronic Science and Technology of China; Robert H. Deng, Singapore Management University

Private set union (PSU) enables two parties to compute the union of their sets without revealing additional information. Jia et al. (USENIX Security 2024) point out that most scalable PSU protocols suffer from during-execution leakage, whereby membership information is revealed to the receiver before the protocol completes, and consequently introduce the functionality of enhanced PSU to mitigate this issue. While several recent works propose protocols for enhanced PSU, existing solutions either incur high computational overhead due to reliance on computation-intensive public-key primitives, or suffer from large communication costs arising from generic secure computation.

In this work, we present a modular framework for constructing enhanced PSU based on the multi-query secret-shared private membership test (ssPMT) protocol (ASIACRYPT 2023) and a new primitive called secret-shared oblivious transfer with default (ssOTd). Our framework eliminates duringexecution leakage by ensuring that all intermediate information remains secret-shared between the parties throughout the protocol. At its core, we present two efficient ssPMT constructions relying primarily on lightweight symmetric-key primitives. We further design a customized, communication-efficient ssOTd protocol to optimize the overhead of enhanced PSU. As a byproduct, we obtain a computation-efficient construction of multi-query reverse PMT (mqRPMT) that avoids the computation-heavy public-key primitives used in the stateof-the-art approaches.

We implement two enhanced PSU protocols, denoted as ePSU-fast and ePSU-low, which are optimized for computational efficiency and communication efficiency, respectively, making them suitable for different network settings. Extensive evaluations show that ePSU-low simultaneously achieves lower computation and communication overhead than the state-of-the-art protocols by Jia et al. (USENIX Security 2024) and Tu et al. (USENIX Security 2025). Moreover, the ePSUfast protocol further reduces computation costs compared to ePSU-low, at the expense of increased communication.

USENIX Security '26 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {320653,
author = {Meng Hao and Guodong Wang and Xinpeng Yang and Pengzhi Xing and Hanxiao Chen and Tianwei Zhang and Haiyang Xue and Guomin Yang and Hongwei Li and Robert H. Deng},
title = {Enhanced Private Set Union from Secret-shared Private Membership Test},
booktitle = {35th USENIX Security Symposium (USENIX Security 26)},
year = {2026},
isbn = {978-1-939133-58-8},
address = {Baltimore, MD},
pages = {2883--2902},
url = {https://www.usenix.org/conference/usenixsecurity26/presentation/hao},
publisher = {USENIX Association},
month = aug
}