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

Diego F. Aranha; Felix Engelmann; Sebastian Kolby; Sophia Yakoubov

Paper 2022/867

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

Diego F. Aranha

, Aarhus University

Felix Engelmann, IT University of Copenhagen

Sebastian Kolby, Aarhus University

Sophia Yakoubov

, Aarhus University

Abstract

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.

Note: Updating the PDF to restore appendixes.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. SCN 2022
DOI: 10.1007/978-3-031-14791-3_17
Keywords: homomorphic signatures union-only signature schemes anonymity software implementation
Contact author(s): dfaranha @ cs au dk
fe-research @ nlogn org
sk @ cs au dk
sophia yakoubov @ cs au dk
History: 2024-11-08: last of 2 revisions; 2022-07-02: received; See all versions
Short URL: https://ia.cr/2022/867
License: CC BY

BibTeX

@misc{cryptoeprint:2022/867,
      author = {Diego F. Aranha and Felix Engelmann and Sebastian Kolby and Sophia Yakoubov},
      title = {The State of the Union: Union-Only Signatures for Data Aggregation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/867},
      year = {2022},
      doi = {10.1007/978-3-031-14791-3_17},
      url = {https://eprint.iacr.org/2022/867}
}