Some properties of $τ$-adic expansions on hyperelliptic Koblitz curves
This work addresses a theoretical gap in hyperelliptic curve cryptography, which is incremental as it extends known properties from elliptic to hyperelliptic curves.
This paper investigates whether two generalizations of τ-NAF for hyperelliptic Koblitz curves possess existence, uniqueness, and minimal Hamming weight properties, finding that the first generalization has only existence and the second has existence and uniqueness, with 16 digit sets identified to achieve the latter.
This paper explores two techniques on a family of hyperelliptic curves that have been proposed to accelerate computation of scalar multiplication for hyperelliptic curve cryptosystems. In elliptic curve cryptosystems, it is known that Koblitz curves admit fast scalar multiplication, namely, the $τ$-adic non-adjacent form ($τ$-NAF). It is shown that the $τ$-NAF has the three properties: (1) existence, (2) uniqueness, and (3) minimality of the Hamming weight. These properties are not only of intrinsic mathematical interest, but also desirable in some cryptographic applications. On the other hand, G{ü}nther, Lange, and Stein have proposed two generalizations of $τ$-NAF for a family of hyperelliptic curves, called \emph{hyperelliptic Koblitz curves}. However, to our knowledge, it is not known whether the three properties are true or not. We provide an answer to the question. Our investigation shows that the first one has only the existence and the second one has the existence and uniqueness. Furthermore, we shall prove that there exist 16 digit sets so that one can achieve the second one.