07. June 2012

Analysis of the width-w non-adjacent form in conjunction with hyperelliptic curve cryptography


One main operation in hyperelliptic curve cryptography is building multiples of a point on a hyperelliptic curve over a finite field. Clearly, we want to perform that scalar multiplication as efficiently as possible. A standard method there are double-and-add algorithms. But if the hyperelliptic curve is defined over a field with q elements and we are working in the point group in an extension (i.e., working over a field with q^m elements), then one can use a Frobenius-and-add method instead. There the (expensive) doublings are replaced by the (cheap) evaluation of the Frobenius endomorphism in the point group. To use that method we need to understand digital expansions with base~tau, where tau is an algebraic integer whose conjugates all have the same absolute value.

So let’s consider digital expansions with a base as above. Let w be a positive integer. Our digit set should consist of 0 and one representative of every residue class modulo tau^w which is not divisible by tau. That choice of the digit set yields redundancy, i.e., each element of Z[tau] has more than one representation. The width-w non-adjacent form, w-NAF for short, is a special representation: Every block of w consecutive digits contains at most one non-zero digit. The choice of the digit set guarantees that the w-NAF-expansion is unique. The low weight (number of non-zero digits) of that expansion makes the arithmetic on the hyperelliptic curves efficient.

The presented work deals with analyzing the number of occurrences of a digit. The main result is an asymptotic formula for the number of occurrences of a fixed non-zero digit in some region (e.g. a ball around 0). The main term of that formula coincides with the full block length analysis given in a recent work. There an explicit expression for the expectation and variance of the occurrence of such a digit in all expansions of a fixed length is given. But the result here is more precise: A periodic fluctuation in the second order term is also exhibited. The proof follows Delange’s method, but several technical problems have to be taken into account.