## Abstract

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.

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.

Originalsprog | Engelsk |
---|---|

Titel | International Conference on Security and Cryptography for Networks |

Publikationsdato | 15 sep. 2022 |

DOI | |

Status | Udgivet - 15 sep. 2022 |