Paper 2002/175

Aggregate and Verifiably Encrypted Signatures from Bilinear Maps

Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham

Abstract

An aggregate signature scheme is a digital signature that supports aggregation: Given $n$ signatures on $n$ distinct messages from $n$ distinct users, it is possible to aggregate all these signatures into a single short signature. This single signature (and the $n$ original messages) will convince the verifier that the $n$ users did indeed sign the $n$ original messages (i.e., user $i$ signed message $M_i$ for $i=1,\ldots,n$). In this paper we introduce the concept of an aggregate signature scheme, present security models for such signatures, and give several applications for aggregate signatures. We construct an efficient aggregate signature from a recent short signature scheme based on bilinear maps due to Boneh, Lynn, and Shacham. Aggregate signatures are useful for reducing the size of certificate chains (by aggregating all signatures in the chain) and for reducing message size in secure routing protocols such as SBGP. We also show that aggregate signatures give rise to verifiably encrypted signatures. Such signatures enable the verifier to test that a given ciphertext $C$ is the encryption of a signature on a given message $M$. Verifiably encrypted signatures are used in contract-signing protocols. Finally, we show that similar ideas can be used to extend the short signature scheme to give simple ring signatures.

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Extended abstract in proceedings of Eurocrypt 2003
Keywords
aggregate signaturesmultisignaturesverifiable encryptionring signaturesbilinear maps
Contact author(s)
hovav @ cs stanford edu
History
2003-04-29: revised
2002-11-16: received
See all versions
Short URL
https://ia.cr/2002/175
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/175,
      author = {Dan Boneh and Craig Gentry and Ben Lynn and Hovav Shacham},
      title = {Aggregate and Verifiably Encrypted Signatures from Bilinear Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2002/175},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/175}},
      url = {https://eprint.iacr.org/2002/175}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.