Paper 2026/1042

Doubly Aggregatable Signatures

Abstract

Multi-signatures allow many signers to jointly generate a single (short) signature on a message. In this context, we introduce doubly aggregatable signatures, a new primitive that consists of two sets of signers. It enables a layer-1 signer to create a succinct attestation, called the layer-1 signature, to the set of observed layer-0 signatures on the same message, and publicly aggregate many layer-1 signatures into a succinct certificate. This certificate can be verified against the public keys, the message, and a bit map of “who observed whom”. Our security model captures both the standard notion of unforgeability (i.e., the adversary cannot forge layer-0 or layer-1 signatures on behalf of honest parties), and resistance to equivocation attacks, where the adversary tries to create a layer-1 signature attesting to layer-0 signatures it has not observed. We give two concretely efficient constructions in the random-oracle model, both of which attain constant-size aggregate layer-1 signatures. The first scheme enables verification using only group additions and two pairings, but requires linear-sized layer-1 public keys per party. The second scheme achieves constant-size public keys, but requires a linear number of pairings for verification. By leveraging the random modular subset sum (RMSS) problem, both schemes attain purely algebraic verification, enabling commit-and-prove SNARKs to check succinct predicates on the bit map. A major application of doubly aggregatable signatures is incentivizing timely all-to-all vote dissemination in consensus protocols. We demonstrate the concrete efficiency of our schemes with a prototype implementation.