Paper 2005/225
Minimality of the Hamming Weight of the \tauNAF for Koblitz Curves and Improved Combination with Point Halving
Roberto M. Avanzi, Clemens Heuberger, and Helmut Prodinger
Abstract
In order to efficiently perform scalar multiplications on elliptic Koblitz curves, expansions of the scalar to a complex base associated with the Frobenius endomorphism are commonly used. One such expansion is the $\tau$adic NAF, introduced by Solinas. Some properties of this expansion, such as the average weight, are well known, but in the literature there is no proof of its {\em optimality}, i.e.~that it always has minimal weight. In this paper we provide the first proof of this fact. Point halving, being faster than doubling, is also used to perform fast scalar multiplications on generic elliptic curves over binary fields. Since its computation is more expensive than that of the Frobenius, halving was thought to be uninteresting for Koblitz curves. At PKC 2004, Avanzi, Ciet, and Sica combined Frobenius operations with one point halving to compute scalar multiplications on Koblitz curves using on average 14\% less group additions than with the usual $\tau$andadd method without increasing memory usage. The second result of this paper is an improvement over their expansion, that is simpler to compute, and optimal in a suitable sense, i.e.\ it has minimal Hamming weight among all $\tau$adic expansions with digits $\{0,\pm1\}$ that allow one halving to be inserted in the corresponding scalar multiplication algorithm. The resulting scalar multiplication requires on average 25\% less group operations than the Frobenius method, and is thus 12.5\% faster than the previous known combination.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 elliptic curve cryptosystemkoblitz curvesscalar multiplicationpoint halving
 Contact author(s)
 roberto avanzi @ gmail com
 History
 20050712: received
 Short URL
 https://ia.cr/2005/225
 License

CC BY
BibTeX
@misc{cryptoeprint:2005/225, author = {Roberto M. Avanzi and Clemens Heuberger and Helmut Prodinger}, title = {Minimality of the Hamming Weight of the \tauNAF for Koblitz Curves and Improved Combination with Point Halving}, howpublished = {Cryptology ePrint Archive, Paper 2005/225}, year = {2005}, note = {\url{https://eprint.iacr.org/2005/225}}, url = {https://eprint.iacr.org/2005/225} }