Paper 2026/1497

Updatable Private Set Union: Generic Construction with Efficient Instantiation

Abstract

Private set union~(PSU) allows two parties to compute the union of their private sets without revealing their intersection. In many real-world applications, parties' datasets undergo frequent updates as elements are added or removed over time. Existing PSU protocols, however, must recompute the entire union from scratch whenever either party's set changes. This becomes highly inefficient when updates are small or frequent relative to the original set sizes. In this paper, we introduce the first updatable PSU~(uPSU) protocol for the standard two-party setting, which supports efficient incremental updates. We present a systematic classification of all possible update scenarios, which shows that only a small subset of updated elements actually modify the union, and establish the leakage baseline for uPSU. Based on these classification and leakage baseline, we provide a generic construction for uPSU that uses existing PSI and a tagged variant of PSU as building blocks. We prove security against semi-honest adversaries in the simulation-based model, and guarantee that incremental updates reveal no more information than a fresh execution of a standard PSU protocol on the updated sets. We instantiate and implement our generic construction using Kim et al.'s PSU protocol~(ACM SAC 2026) and Raghuraman and Rindal's PSI protocol~(ACM CCS 2022), demonstrating significant performance improvements over full recomputation of the union, even though its cost still depends on the original set size rather than purely on the update size. For set size $n = 2^{20}$ and update size $t = 2^{12}$, our protocol achieves a 14.1--45.4$\times$ speedup with a 4.8--59.1$\times$ communication reduction over full recomputation using baseline PSU protocols.