Cryptology ePrint Archive: Report 2018/070

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

Craig Gentry and Adam O'Neill and Leonid Reyzin

Abstract: 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.

Category / Keywords: Aggregate signatures, trapdoor permutations, ideal cipher model

Original Publication (in the same form): IACR-PKC-2018

Date: received 16 Jan 2018, last revised 16 Jan 2018

Contact author: adam at cs georgetown edu,reyzin@cs bu edu,craigbgentry@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180118:125430 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]