Verifiable Delegation of Private Set Unions Over Dynamic Sets

A delegated private set union (D-PSU) enables users to outsource their private sets to a server while delegating the union computation. Because the server cannot be assumed trustworthy, users require verifiability (assurance that neither the outsourced sets nor the returned union has been tampered with) together with privacy, ensuring that the server learns nothing about the individual sets or the union. Moreover, real-world datasets evolve, so updatability (efficient insertion and deletion of elements) is essential. Existing constructions achieve at most two of these properties: Chung et al. (TDSC 2025) offer privacy and updatability but no verifiability, whereas Li et al. (SIGMOD 2021) offer verifiability but require multiple non-colluding servers and support only static sets. In this work, we propose $\textsf {UV}$ D-PSU, the first single-server D-PSU that simultaneously achieves verifiability, privacy, and updatability. The core of our construction is a combination of fully homomorphic encryption and a multiplicity hash table, an integer vector that stores the multiplicity of each element at the index determined by a perfect hash function. Insertions and deletions rely on symmetric-key primitives only, yielding a per-update cost independent of the set size. We prove that our $\textsf {UV}$ D-PSU protocol is secure in the presence of a malicious server that does not collude with the clients, and we validate its efficiency and feasibility through a prototype implementation and comprehensive experiments. At the largest benchmarked size of $2^{20}$ elements per set, the protocol completes end to end in under 5 seconds on commodity hardware, and a single update costs 6–9 microseconds regardless of the set size.