10. July 2014

When is non-adjacent form not a minimal digit expansion?

Abstract

In the talk we consider redundant tau-adic digit expansion. These expansions come from elliptic curve cryptography, where we want an efficient scalar multiplication of curve-points. One particular expansion leading to fast evaluation schemes is the width-w non-adjacent form (w-NAF).

In the case of integer-bases the w-NAF is an optimal digit expansion, which means that it has minimal Hamming weight. However, this is not always true for arbitrary (algebraic-integer) bases. In particular, looking at bases tau coming from Koblitz curves in characteristic 2, we will see that the width~w non-adjacent form is almost always non-optimal (with very few exceptions). The proof of this result uses tools from Diophantine analysis, namely the theory of linear forms in logarithms and from the geometry of numbers.

We will also look at other bases and see results on the non-optimality, as well as, the optimality of the w-NAF.