Paper 2014/664

On the Optimal Pre-Computation of Window $\tau$NAF for Koblitz Curves

William R. Trost and Guangwu Xu

Abstract

Koblitz curves have been a nice subject of consideration for both theoretical and practical interests. The window $\tau$-adic algorithm of Solinas (window $\tau$NAF) is the most powerful method for computing point multiplication for Koblitz curves. Pre-computation plays an important role in improving the performance of point multiplication. In this paper, the concept of optimal pre-computation for window $\tau$NAF is formulated. In this setting, an optimal pre-computation has some mathematically natural and clean forms, and requires $2^{w-2}-1$ point additions and two evaluations of the Frobenius map $\tau$, where $w$ is the window width. One of the main results of this paper is to construct an optimal pre-computation scheme for each window width $w$ from $4$ to $15$ (more than practical needs). These pre-computations can be easily incorporated into implementations of window $\tau$NAF. The ideas in the paper can also be used to construct other suitable pre-computations. This paper also includes a discussion of coefficient sets for window $\tau$NAF and the divisibility by powers of $\tau$ through different approaches.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
elliptic curve cryptosystemimplementation
Contact author(s)
gxu4uwm @ uwm edu
History
2014-08-28: received
Short URL
https://ia.cr/2014/664
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/664,
      author = {William R.  Trost and Guangwu Xu},
      title = {On the Optimal Pre-Computation of Window $\tau${NAF} for Koblitz Curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/664},
      year = {2014},
      url = {https://eprint.iacr.org/2014/664}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.