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

TY - GEN

T1 - The State of the Union

T2 - 13th Conference on Security and Cryptography For Networks

AU - Aranha, Diego F.

AU - Engelmann, Felix Theodor

AU - Kolby, Sebastian

AU - Yakoubov, Sophia

PY - 2022/9

Y1 - 2022/9

N2 - A union-only signature (UOS) scheme (informally introduced by Johnson et al. at CT-RSA 2002) allows signers to sign sets of messages 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 commitments 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. (A full version of this paper, with all proofs and preliminaries, is available on the ePrint Archive).

AB - A union-only signature (UOS) scheme (informally introduced by Johnson et al. at CT-RSA 2002) allows signers to sign sets of messages 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 commitments 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. (A full version of this paper, with all proofs and preliminaries, is available on the ePrint Archive).

KW - history-hiding

KW - homomorphic signatures

KW - software implementation

KW - union-only signature schemes

U2 - 10.1007/978-3-031-14791-3_17

DO - 10.1007/978-3-031-14791-3_17

M3 - Article in proceedings

SN - 9783031147906

T3 - Lecture Notes in Computer Science

SP - 387

EP - 410

BT - Security and Cryptography for Networks - 13th International Conference, SCN 2022, Proceedings

A2 - Galdi, Clemente

A2 - Jarecki, Stanislaw

PB - Springer

Y2 - 12 September 2022 through 14 September 2022

ER -