Paper 2008/153
Redundant $\tau$-adic Expansions II: Non-Optimality and Chaotic Behaviour
Clemens Heuberger
Abstract
When computing scalar multiples on Koblitz curves, the Frobenius endomorphism can be used to replace the usual doublings on the curve. This involves digital expansions of the scalar to the complex base $\tau=(\pm 1\pm \sqrt{-7})/2$ instead of binary expansions. As in the binary case, this method can be sped up by enlarging the set of valid digits at the cost of precomputing some points on the curve. In the binary case, it is known that a simple syntactical condition (the so-called $w$-NAF-condition) on the expansion ensures that the number of curve additions is minimised. The purpose of this paper is to show that this is not longer true for the base $\tau$ and $w\in\{4,5,6\}$. Even worse, it is shown that there is no longer an online algorithm to compute an optimal expansion from the digits of some standard expansion from the least to the most significant digit, which can be interpreted as chaotic behaviour. The proofs heavily depend on symbolic computations involving transducer automata.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Koblitz curvesFrobenius endomorphismScalar Multiplication$tau$-adic expansionsNon-Adjacent-FormsDigit SetsEfficient Implementation
- Contact author(s)
- clemens heuberger @ tugraz at
- History
- 2008-04-08: received
- Short URL
- https://ia.cr/2008/153
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/153,
author = {Clemens Heuberger},
title = {Redundant $\tau$-adic Expansions II: Non-Optimality and Chaotic Behaviour},
howpublished = {Cryptology ePrint Archive, Paper 2008/153},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/153}},
url = {https://eprint.iacr.org/2008/153}
}
