[Resource Topic] 2025/790: PULSE: Parallel Private Set Union for Large-Scale Entities

Welcome to the resource topic for 2025/790

Title:
PULSE: Parallel Private Set Union for Large-Scale Entities

Authors: Jiahui Gao, Son Nguyen, Marina Blanton, Ni Trieu

Abstract:

Multi-party private set union (mPSU) allows multiple parties to compute the union of their private input sets without revealing any additional information.
Existing efficient mPSU protocols can be categorized into symmetric key encryption (SKE)-based and public key encryption (PKE)-based approaches. However, neither type of mPSU protocol scales efficiently to a large number of parties, as they fail to fully utilize available computational resources, leaving participants idle during various stages of the protocol execution.

This work examines the limitation of existing protocols and proposes a unified framework for designing efficient mPSU protocols. We then introduce an efficient Parallel mPSU for Large-Scale Entities (PULSE) that enables parallel computation, allowing all parties/entities to perform computations without idle time, leading to significant efficiency improvements, particularly as the number of parties increases. Our protocol is based on PKE and secure even when up to n-1 semi-honest parties are corrupted. We implemented PULSE and compared it to state-of-the-art mPSU protocols under different settings, showing a speedup of 1.91 to 3.57\times for n=8 parties for various set sizes.

ePrint: https://eprint.iacr.org/2025/790

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 .