CryptoDB
Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiations
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Modular exponentiation in an abelian group is one of the most frequently used mathematical primitives in modern cryptography. {\em Batch verification} is to verify many exponentiations simultaneously. We propose two fast batch verification algorithms. The first one makes use of exponents with small weight, called {\em sparse exponents}, which is asymptotically 10 times faster than the individual verification and twice faster than the previous works without security loss. The second one is applied only to elliptic curves defined over small finite fields. Using sparse Frobenius expansion with small integer coefficients, we propose a complex exponent test which is four times faster than the previous works. For example, each exponentiation in one batch requires asymptotically 9 elliptic curve additions in some elliptic curves for $2^{80}$ security. |
BibTeX
@misc{eprint-2005-12610,
title={Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiations},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / Batch verification, modular exponentiation, sparse exponent, Frobenius map},
url={http://eprint.iacr.org/2005/276},
note={ dlee@etri.re.kr 13013 received 17 Aug 2005},
author={Jung Hee Cheon and Dong Hoon Lee},
year=2005
}