Paper 2011/318

Scalar Multiplication on Koblitz Curves using $\tau^2-$NAF

Sujoy Sinha Roy, Chester Rebeiro, Debdeep Mukhopadhyay, Junko Takahashi, and Toshinori Fukunaga

Abstract

The paper proposes a $\tau^2-$NAF method for scalar multiplication on Koblitz curves, which requires asymptotically $0.215m$ point additions in $GF(2^m)$. For $\tau^2-$NAF method, point quading operation $(a\rightarrow a^4)$ is performed instead of point squarings. The proposed method is faster than normal $\tau-$NAF method, which requires around $\frac{m}{3}$ point additions. However, like width $w$ based $\tau-$NAF methods, there is an overhead of pre-computations in the $\tau^2-$NAF method. For extended binary fields of small size, the $\tau^2-$NAF based scalar multiplication requires almost same number of point additions as in width $4$ $\tau-$NAF method. Though, complexity wise, $\tau^2-$NAF based scalar multiplication and width $4-\tau-$NAF based scalar multiplication are similar, but the techniques are different.