Welcome to the resource topic for 2021/171
Title:
Pre-Computation Scheme of Window $\tau$NAF for Koblitz Curves Revisited
Authors: Wei Yu, 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.
ePrint: https://eprint.iacr.org/2021/171
Talk: https://www.youtube.com/watch?v=apSYUZ7CV-I
Slides: https://iacr.org/submit/files/slides/2021/eurocrypt/eurocrypt2021/4/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .