Wide-w-NAF Method for Scalar Multiplication on Koblitz Curves

Abstract

At CRYPTO 1991, Koblitz proposed the anomalous binary curves for speeding up scalar multiplication in elliptic curve cryptosystem. At CRYPTO 1997, Solinas proposed the tau-NAF method on Koblitz curves and reduced the Hamming weight of the scalar to n/3 over the field F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> n. At PKC 2004, Avanzi et al combined the tau-NAF with one point halving and reduced the Hamming weight of the scalar to 2n/7. Recently, Avanzi et al improved this method by introducing the wide-double-NAF whose Hamming weight is n/4. In this paper, we propose the wide-w-NAF, which is an extension of Avanzi's wide-double-NAF, and reduce the Hamming weight to n/(w + 1). When n > 144, our method is at least 43%-56% faster than Solinas's tau-NAF method and 21%-39% faster than Avanzi's wide-double-NAF method without additional memory requirements.