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.Category / Keywords: foundations / multi-exponentiation, algorithms, public-key cryptography, signatures, elliptic curve cryptosystems, hyperelliptic curve cryptosystems, trace zero varieties, XTR Date: received 12 Oct 2002, last revised 28 Oct 2002 Contact author: mocenigo at exp-math uni-essen de Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation 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.Version: 20021028:203003 (All versions of this report) Discussion forum: Show discussion | Start new discussion