Paper 2003/091

Sequential Aggregate Signatures from Trapdoor Permutations

Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, and Hovav Shacham


An aggregate signature scheme (recently proposed by Boneh, Gentry, Lynn and Shacham) is a method for combining $n$ signatures from $n$ different signers on $n$ different messages into one signature of unit length. We propose \emph{sequential aggregate signatures}, in which the set of signers is ordered. The aggregate signature is computed by having each signer, in turn, add his signature to it. We show how to realize this in such a way that the size of the aggregate signature is independent of $n$. This makes sequential aggregate signatures a natural primitive for certificate chains, whose length can be reduced by aggregating all signatures in a chain. We give a construction based on families of certified trapdoor permutations, and show how to instantiate our scheme based on RSA.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Extended abstract in Proceedings of Eurocrypt 2004, pp. 74-90
RSAsignature schemesaggregate signatures
Contact author(s)
hovav @ cs stanford edu
2004-06-09: last of 2 revisions
2003-05-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anna Lysyanskaya and Silvio Micali and Leonid Reyzin and Hovav Shacham},
      title = {Sequential Aggregate Signatures from Trapdoor Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2003/091},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.