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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Published in IEEE Transactions on Computers, vol.55 (no.12), pp.1536-1542, (December 2006)
Keywords
Batch verificationmodular exponentiationsparse exponentFrobenius map
Contact author(s)
dlee @ ensec re kr
History
2008-08-06: revised
2005-08-18: received
See all versions
Short URL
https://ia.cr/2005/276
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/276,
      author = {Jung Hee Cheon and Dong Hoon Lee},
      title = {Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiations},
      howpublished = {Cryptology ePrint Archive, Paper 2005/276},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/276}},
      url = {https://eprint.iacr.org/2005/276}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.