Welcome to the resource topic for
**2005/225**

**Title:**

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

**Authors:**
Roberto M. Avanzi, Clemens Heuberger, 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.

**ePrint:**
https://eprint.iacr.org/2005/225

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .