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.