Paper 2018/070

A Unified Framework for Trapdoor-Permutation-Based Sequential Aggregate Signatures

Craig Gentry, Adam O'Neill, and Leonid Reyzin


We give a framework for trapdoor-permutation-based sequential aggregate signatures (SAS) that unifies and simplifies prior work and leads to new results. The framework is based on ideal ciphers over large domains, which have recently been shown to be realizable in the random oracle model. The basic idea is to replace the random oracle in the full-domain-hash signature scheme with an ideal cipher. Each signer in sequence applies the ideal cipher, keyed by the message, to the output of the previous signer, and then inverts the trapdoor permutation on the result. We obtain different variants of the scheme by varying additional keying material in the ideal cipher and making different assumptions on the trapdoor permutation. In particular, we obtain the first scheme with lazy verification and signature size independent of the number of signers that does not rely on bilinear pairings. Since existing proofs that ideal ciphers over large domains can be realized in the random oracle model are lossy, our schemes do not currently permit practical instantiation parameters at a reasonable security level, and thus we view our contribution as mainly conceptual. However, we are optimistic tighter proofs will be found, at least in our specific application.

Available format(s)
Publication info
Published by the IACR in PKC 2018
Aggregate signaturestrapdoor permutationsideal cipher model
Contact author(s)
adam @ cs georgetown edu
reyzin @ cs bu edu
craigbgentry @ gmail com
2018-01-18: received
Short URL
Creative Commons Attribution


      author = {Craig Gentry and Adam O'Neill and Leonid Reyzin},
      title = {A Unified Framework for Trapdoor-Permutation-Based Sequential Aggregate Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2018/070},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.