[Resource Topic] 2005/276: Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiations

Welcome to the resource topic for 2005/276

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

Authors: Jung Hee Cheon, 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.

ePrint: https://eprint.iacr.org/2005/276

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .