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

*Jung Hee Cheon and Dong Hoon Lee*

**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.

**Category / Keywords: **public-key cryptography / Batch verification, modular exponentiation, sparse exponent, Frobenius map

**Publication Info: **Published in IEEE Transactions on Computers, vol.55 (no.12), pp.1536-1542, (December 2006)

**Date: **received 17 Aug 2005, last revised 6 Aug 2008

**Contact author: **dlee at ensec re kr

**Available format(s): **PDF | BibTeX Citation

**Version: **20080806:211423 (All versions of this report)

**Short URL: **ia.cr/2005/276

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]