Paper 1998/007

Fast Batch Verification for Modular Exponentiation and Digital Signatures

Mihir Bellare, Juan A. Garay, and Tal Rabin

Abstract

Many tasks in cryptography (e.g., digital signature verification) call for verification of a basic operation like modular exponentiation in some group: given (g,x,y) check that g<sup>x</sup>=y. This is typically done by re-computing g<sup>x</sup> and checking we get y. We would like to do it differently, and faster. The approach we use is batching. Focusing first on the basic modular exponentiation operation, we provide some probabilistic batch verifiers, or tests, that verify a sequence of modular exponentiations significantly faster than the naive re-computation method. This yields speedups for several verification tasks that involve modular exponentiations. Focusing specifically on digital signatures, we then suggest a weaker notion of (batch) verification which we call ``screening.'' It seems useful for many usages of signatures, and has the advantage that it can be done very fast; in particular, we show how to screen a sequence of RSA signatures at the cost of one RSA verification plus hashing.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords
Modular exponentiationdigital signaturesverificationRSADSSbatchingprogram checking.
Contact author(s)
mihir @ cs ucsd edu
History
1998-06-16: revised
1998-03-08: received
Short URL
https://ia.cr/1998/007
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1998/007,
      author = {Mihir Bellare and Juan A.  Garay and Tal Rabin},
      title = {Fast Batch Verification for Modular Exponentiation and Digital Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 1998/007},
      year = {1998},
      url = {https://eprint.iacr.org/1998/007}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.