Wide-w-NAF Method for Scalar Multiplication on Koblitz Curves
Ming Li, Baodong Qin, Fanyu Kong, Daxing Li · 2007
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 F2n. 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.