Pre-computation Scheme of Window τNAF for Koblitz Curves Revisited

摘要

Let E_a/F_2 : y~2 + xy = x~3 + ax~2 + 1 be a Koblitz curve. The window τ-adic non-adjacent form (window τNAF) is currently the standard representation system to perform scalar multiplications on E_a/F_2~m utilizing the Frobenius map τ. This work focuses on the pre-computation part of scalar multiplication. We first introduce μτ-operations where μ = (-1)~(1-a) and τ is the complex conjugate of τ. Efficient formulas of μτ-operations are then derived and used in a novel pre-computation scheme. Our pre-computation scheme requires 6M + 6S, 18M + 17S, 44M + 32S, and 88M + 62S (a = 0) and 6M + 6S, 19M + 17S, 46M + 32S, and 90M + 62S (a = 1) for window τNAF with widths from 4 to 7 respectively. It is about two times faster, compared to the state-of-the-art technique of pre-computation in the literature. The impact of our new efficient pre-computation is also reflected by the significant improvement of scalar multiplication. Traditionally, window τNAF with width at most 6 is used to achieve the best scalar multiplication. Because of the dramatic cost reduction of the proposed pre-computation, we are able to increase the width for window τNAF to 7 for a better scalar multiplication. This indicates that the pre-computation part becomes more important in performing scalar multiplication. With our efficient pre-computation and the new window width, our scalar multiplication runs in at least 85.2% the time of Kohel's work (Eurocrypt'2017) combining the best previous pre-computation. Our results push the scalar multiplication of Koblitz curves, a very well-studied and long-standing research area, to a significant new stage.