Asymmetric Multi-Party Private Set Union for Large-Repository Updates Without Non-Collusion Assumptions
Yuqi Jia, Leyou Zhang · Cryptography · 2026
Multi-party private set union (MPSU) allows multiple parties to compute a union without disclosing private inputs, but most existing protocols focus on balanced settings with comparable input sizes. In large-repository update scenarios, a leader maintains a massive base set while contributors submit small update sets; directly using balanced MPSU makes the online cost scale with the leader’s repository size. We propose AegisUnion, an asymmetric MPSU protocol tailored to large-repository updates. AegisUnion separates repository-dependent computation from online update processing through an offline oblivious key-value store (OKVS) encoding phase. In the online phase, contributors perform private membership determination, cross-contributor private deduplication, conditional payload sharing, and secret-shared shuffling, without revealing raw inputs, repository-overlap relations, inter-contributor duplicates, or the source of each output element. Under the semi-honest model, AegisUnion tolerates any coalition of corrupted parties as long as at least one party remains honest, without non-collusion assumptions. Experiments show that, as the repository grows from 214 to 218, the online time remains stable at 663–715 ms. At repository size 218 and contributor update bound 210, AegisUnion achieves about 455× and 454× lower online time than symmetric-key-based MPSU and public-key-based MPSU baselines, respectively, and about 271× and 575× lower online communication.