Welcome to the resource topic for 1998/007
Title:
Fast Batch Verification for Modular Exponentiation and Digital Signatures
Authors: Mihir Bellare, Juan A. Garay, 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 gx=y.
This is typically done by re-computing gx 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.
ePrint: https://eprint.iacr.org/1998/007
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .