Paper 2002/154

On multi-exponentiation in cryptography

Roberto M. Avanzi

Abstract

We describe and analyze new combinations of multi-exponentiation algorithms with representations of the exponents. We deal mainly but not exclusively with the case where the inversion of group elements is fast: These methods are most attractive with exponents in the range from 80 to 256 bits, and can also be used for computing single exponentiations in groups which admit an automorphism satisfying a monic equation of small degree over the integers. The choice of suitable exponent representations allows us to match or improve the running time of the best multi-exponentiation techniques in the aforementioned range, while keeping the memory requirements as small as possible. Hence some of the methods presented here are particularly attractive for deployment in memory constrained environments such as smart cards. By construction, such methods provide good resistance against side channel attacks. We also describe some applications of these algorithms.

Note: This is the first in a series of papers which explore different aspects of exponentiation and multi-exponentiation in cryptography. This research has been supported by the European Commission's Fifth Framework Program, under contract IST - 2001 - 32613. See http://www.arehcc.com This is a slightly revised version of the original submission. In particular the introduction (which is now separated from the description of the algorithms) and the description of applications have been improved.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
multi-exponentiationalgorithmspublic-key cryptographysignatureselliptic curve cryptosystemshyperelliptic curve cryptosystemstrace zero varietiesXTR
Contact author(s)
mocenigo @ exp-math uni-essen de
History
2002-10-28: last of 2 revisions
2002-10-15: received
See all versions
Short URL
https://ia.cr/2002/154
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/154,
      author = {Roberto M.  Avanzi},
      title = {On multi-exponentiation in cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2002/154},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/154}},
      url = {https://eprint.iacr.org/2002/154}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.