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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Koblitz curveelliptic curvescalar multiplicationtau^2 NAF
Contact author(s)
sujoyetc @ cse iitkgp ernet in
chester @ cse iitkgp ernet in
debdeep @ cse iitkgp ernet in
takahashi junko @ lab ntt co jp
toshi fukunaga @ hco ntt co jp
History
2011-06-17: received
Short URL
https://ia.cr/2011/318
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/318,
      author = {Sujoy Sinha Roy and Chester Rebeiro and Debdeep Mukhopadhyay and Junko Takahashi and Toshinori Fukunaga},
      title = {Scalar Multiplication on Koblitz Curves using $\tau^2-$NAF},
      howpublished = {Cryptology ePrint Archive, Paper 2011/318},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/318}},
      url = {https://eprint.iacr.org/2011/318}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.