Authors
Mihir Bellare, Juan A Garay, Tal Rabin
Publication date
1998
Conference
Advances in Cryptology—EUROCRYPT'98: International Conference on the Theory and Application of Cryptographic Techniques Espoo, Finland, May 31–June 4, 1998 Proceedings 17
Pages
236-250
Publisher
Springer Berlin Heidelberg
Description
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 …
Total citations
Scholar articles
M Bellare, JA Garay, T Rabin - … —EUROCRYPT'98: International Conference on the …, 1998