Paper 2021/171

Pre-Computation Scheme of Window $\tau$NAF for Koblitz Curves Revisited

Wei Yu and Guangwu Xu

Abstract

Let $E_a/ \mathbb{F}_{2}: y^2+xy=x^3+ax^2+1$ be a Koblitz curve. The window $\tau$-adic non-adjacent form (window $\tau$NAF) is currently the standard representation system to perform scalar multiplications on $E_a/ \mathbb{F}_{2^m}$ utilizing the Frobenius map $\tau$. This work focuses on the pre-computation part of scalar multiplication. We first introduce $\mu\bar{\tau}$-operations where $\mu=(-1)^{1-a}$ and $\bar{\tau}$ is the complex conjugate of $\tau$. Efficient formulas of $\mu\bar{\tau}$-operations are then derived and used in a novel pre-computation scheme. Our pre-computation scheme requires $6${\bf M}$+6${\bf S}, $18${\bf M}$+17${\bf S}, $44${\bf M}$+32${\bf S}, and $88${\bf M}$+62${\bf S} ($a=0$) and $6${\bf M}$+6${\bf S}, $19${\bf M}$+17${\bf S}, $46${\bf M}$+32${\bf S}, and $90${\bf M}$+62${\bf S} ($a=1$) for window $\tau$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 $\tau$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 $\tau$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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2021
Keywords
elliptic curve cryptosystem
Contact author(s)
yuwei_1_yw @ 163 com
History
2021-02-17: received
Short URL
https://ia.cr/2021/171
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/171,
      author = {Wei Yu and Guangwu Xu},
      title = {Pre-Computation Scheme of Window $\tau$NAF for Koblitz Curves Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2021/171},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/171}},
      url = {https://eprint.iacr.org/2021/171}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.