Paper 2008/063

Efficient Sequential Aggregate Signed Data

Gregory Neven

Abstract

We generalize the concept of sequential aggregate signatures (SAS), proposed by Lysyanskaya, Micali, Reyzin, and Shacham at Eurocrypt 2004, to a new primitive called sequential aggregate signed data (SASD) that tries to minimize the total amount of transmitted data, rather than just signature length. We present SAS and SASD schemes that offer numerous advantages over the scheme of Lysyanskaya et al. Most importantly, our schemes can be instantiated with uncertified claw-free permutations, thereby allowing implementations based on low-exponent RSA and factoring, and drastically reducing signing and verification costs. Our schemes support aggregation of signatures under keys of different lengths, and the SASD scheme even has as little as 160 bits of bandwidth overhead. Finally, we present a multi-signed data scheme that, when compared to the state-of-the-art multi-signature schemes, is the first scheme with non-interactive signature generation not based on pairings. All of our constructions are proved secure in the random oracle model based on families of claw-free permutations.

Note: Oct 12, 2010: Minor updates.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. To appear in IEEE Transactions on Information Theory. An extended abstract appeared at Eurocrypt 2008.
Keywords
Aggregate signaturesRSAprovable security.
Contact author(s)
gregory @ neven org
History
2010-10-12: revised
2008-02-11: received
See all versions
Short URL
https://ia.cr/2008/063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/063,
      author = {Gregory Neven},
      title = {Efficient Sequential Aggregate Signed Data},
      howpublished = {Cryptology ePrint Archive, Paper 2008/063},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/063}},
      url = {https://eprint.iacr.org/2008/063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.