A Survey of Two Signature Aggregation Techniques

Authors: D. Boneh, C. Gentry, B. Lynn, and H. Shacham

We survey two recent signature constructions that support signature aggregation: Given n signatures on n distinct messages from n distinct users, it is possible to aggregate all these signatures into a single signature. This single signature (and all n original messages) will convince any verifier that the n users signed the n original messages (i.e., for i=1,...,n user i signed message number i). We survey two constructions. The first is based on the short signature scheme of Boneh, Lynn, and Shacham and supports general aggregation. The second, based on a multisignature scheme of Micali, Ohta, and Reyzin, is built from any trapdoor permutation but only supports sequential aggregation. Aggregate signatures are useful for reducing the size of certificate chains (by aggregating all signatures in the chain) and for reducing message size in secure routing protocols such as SBGP.

In CryptoBytes Vol. 6, No. 2, 2003

Full paper: pdf         [first posted 8/2003 ]

Related papers: See the full aggregate signatures paper.