Paper 2007/172

Batch Verification of Short Signatures

Jan Camenisch, Susan Hohenberger, and Michael Østergaard Pedersen

Abstract

With computer networks spreading into a variety of new environments, the need to authenticate and secure communication grows. Many of these new environments have particular requirements on the applicable cryptographic primitives. For instance, several applications require that communication overhead be small and that many messages be processed at the same time. In this paper we consider the suitability of public key signatures in the latter scenario. That is, we consider signatures that are 1) short and 2) where many signatures from (possibly) different signers on (possibly) different messages can be verified quickly. Prior work focused almost exclusively on batching signatures from the same signer. We propose the first batch verifier for messages from many (certified) signers without random oracles and with a verification time where the dominant operation is independent of the number of signatures to verify. We further propose a new signature scheme with very short signatures, for which batch verification for many signers is also highly efficient. Combining our new signatures with the best known techniques for batching certificates from the same authority, we get a fast batch verifier for certificates and messages combined. Although our new signature scheme has some restrictions, it is very efficient and still practical for some communication applications.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Full version of the Eurocrypt 2007 paper
Keywords
signaturesbatch verificationscreeningvehicular networks
Contact author(s)
michael @ daimi au dk
History
2009-09-03: last of 8 revisions
2007-05-12: received
See all versions
Short URL
https://ia.cr/2007/172
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/172,
      author = {Jan Camenisch and Susan Hohenberger and Michael Østergaard Pedersen},
      title = {Batch Verification of Short Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2007/172},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/172}},
      url = {https://eprint.iacr.org/2007/172}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.