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\to 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 $$NAF based scalar multiplication requires almost same number of point additions as in width $$ $$NAF method. Though, complexity wise, $$NAF based scalar multiplication and width $$NAF based scalar multiplication are similar, but the techniques are different.