International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 28 August 2014

William R. Trost, Guangwu Xu
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.