### Two Methods of Signature Aggregation

Hovav Shacham
*Stanford*

Aggregate signatures are a new primitive whereby a single aggregate
signature, the same length as an ordinary signature, stands for
several signatures by several signers on several messages. Aggregate
signatures are an extension of multisignatures. In a multisignature,
either all signers or all messages must be the same. Aggregate
signatures have applications in X.509 certificate chains, SBGP secure
routing, and PGP webs of trust.
We describe two methods of constructing aggregate signatures:
aggregate signatures and sequential aggregate signatures.
The aggregate signature scheme employs a bilinear map and is related
to Boneh-Lynn-Shacham GDH signatures and their Boldyreva
multisignature variant. In this construction, ordinary GDH signatures
by several signers can be combined into an aggregate signature by an
unrelated, untrusted party.
The Sequential aggregate signature scheme employs a family of trapdoor
permutations, and is related to full-domain hash signatures. In
particular, it can be instantiated using the RSA function. In this
construction, aggregation and signing are combined into a single
operation, and must be performed incrementally by the individual
signers. Sequential aggregate signatures can thus be constructed from
more general assumptions, but are useful for only some of the
applications of aggregate signatures.