Paper 2017/1020

A Novel Pre-Computation Scheme of Window τNAF for Koblitz Curves

Wei Yu, Saud Al Musa, Guangwu Xu, and Bao Li

Abstract

Let Ea:y2+xy=x3+ax2+1/F2m be a Koblitz curve. The window τ-adic nonadjacent-form (window τNAF) is currently the standard representation system to perform scalar multiplications on Ea by utilizing the Frobenius map τ. Pre-computation is an important part for the window τNAF. In this paper, we first introduce μτ¯-operations in lambda coordinates (μ=(1)1a and τ¯ is the complex conjugate of the complex representation of ). Efficient formulas of -operations are then derived and used in a novel pre-computation scheme to improve the efficiency of scalar multiplications using window NAF. Our pre-computation scheme costs MS, MS, and MS for window NAF with width , , and respectively whereas the pre-computation with the state-of-the-art technique costs MS, MS, and MS. Experimental results show that our pre-computation is about faster, compared to the best pre-computation in the literature. It also shows that we can save from to on the scalar multiplications using window NAF with our pre-computation.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Elliptic curve cryptographyKoblitz curveWindow NAFPre-computationLambda coordinate
Contact author(s)
yuwei_1_yw @ 163 com
History
2017-10-25: received
Short URL
https://ia.cr/2017/1020
License
Creative Commons Attribution
CC BY

BibTeX

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