Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiations

Modular exponentiation in an abelian group is one of the most frequently used mathematical primitives in modern cryptography. Batch verification is an algorithm for verifying many exponentiations simultaneously. We propose two fast batch verification algorithms. The first one makes use of exponents of small weight, called sparse exponents, and is asymptotically 10 times faster than individual verification and twice as fast as previous works at the same security level. The second one can only be applied to elliptic curves defined over small finite fields. Using sparse Frobenius expansion with small integer coefficients, we give a complex exponent test which is four times faster than the previous works. For example, each exponentiation in one batch asymptotically requires nine elliptic curve additions on some elliptic curves for 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">80</sup> security