** 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^{x}=y. This is
typically done by re-computing g^{x} 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.

** Ref:** Extended abstract was in Advances in Cryptology- Eurocrypt 98
Proceedings, Lecture Notes in Computer Science Vol. 1403, K. Nyberg ed,
Springer-Verlag, 1998. Full paper available below.

** Full paper: ** Available as compressed
postscript, postscript, or
pdf. ( Help if this doesn't work).