## Cryptology ePrint Archive: Report 2005/225

**Minimality of the Hamming Weight of the \tau-NAF for Koblitz Curves and Improved Combination with Point Halving**

*Roberto M. Avanzi and 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$-and-add 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.

**Category / Keywords: **implementation / elliptic curve cryptosystem, koblitz curves, scalar multiplication, point halving

**Date: **received 12 Jul 2005

**Contact author: **roberto avanzi at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20050712:201552 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]