Efficient multi-party private set union resistant to maximum collusion attacks

Multi-party Private Set Union (MPSU) enables multiple parties to compute the union of their private sets while revealing nothing beyond the resulting union. Gao et al. (PETS 2024) proposed an efficient MPSU protocol for large-scale sets that resists maximum semi-honest collusion, where only a designated leader learns the union. Their protocol nevertheless incurs high communication overhead due to transmitting large volumes of threshold re-randomizable public-key encryption (TR-PKE) ciphertexts during interaction. In this work, we design an optimized protocol, Π MPSUᵒne-leader, that reduces communication by using symmetric-key encryption (SKE) for most message payloads and restricting TR-PKE to a few indispensable operations. Security is preserved by separating roles. TR-PKE is used only for set items that require re-randomization and joint threshold decryption, while SKE protects all other messages carrying masked or randomized intermediate payloads. Building on Π MPSUᵒne-leader, we further propose a leaderless protocol, Π MPSUˡeaderless, which allows all parties to obtain the union output and mitigates the risk of a single leader dominating in decentralized deployments. We implement our schemes and conduct a comparison with state-of-the-art. The results demonstrate that Π MPSUᵒne-leader achieves a 4–5× shrinking in communication and a 1.3–1.8× speedup, depending on the set size and the number of parties.