Cryptology ePrint Archive: Report 2005/276

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)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]