The State of the Union: Union-Only Signatures for Data Aggregation

A union-only signature (UOS) scheme (informally introduced
by Johnson et al. at CT-RSA 2002) allows signers to sign sets of mes-
sages in such a way that (1) any third party can merge two signatures to
derive a signature on the union of the message sets, and (2) no adversary,
given a signature on some set, can derive a valid signature on any strict
subset of that set (unless it has seen such a signature already).
Johnson et al. originally posed building a UOS as an open problem. In
this paper, we make two contributions: we give the first formal definition
of a UOS scheme, and we give the first UOS constructions. Our main
construction uses hashing, regular digital signatures, Pedersen commit-
ments and signatures of knowledge. We provide an implementation that
demonstrates its practicality. Our main construction also relies on the
hardness of the short integer solution (SIS) problem; we show how that
this assumption can be replaced with the use of groups of unknown order.
Finally, we sketch a UOS construction using SNARKs; this additionally
gives the property that the size of the signature does not grow with the
number of merges.