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.
Category / Keywords: Modular exponentiation, digital signatures, verification, RSA, DSS, batching, program checking. Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. Date: Received March 8, 1998. Revised June 16th, 1998. Contact author: mihir at cs ucsd edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Discussion forum: Show discussion | Start new discussion