Paper 2017/840

Fast Scalar Multiplication for Elliptic Curves over Binary Fields by Efficiently Computable Formulas

Saud Al Musa and Guangwu Xu

Abstract

This paper considers efficient scalar multiplication of elliptic curves over binary fields with a twofold purpose. Firstly, we derive the most efficient $3P$ formula in $\lambda$-projective coordinates and $5P$ formula in both affine and $\lambda$-projective coordinates. Secondly, extensive experiments have been conducted to test various multi-base scalar multiplication methods (e.g., greedy, ternary/binary, multi-base NAF, and tree-based) by integrating our fast formulas. The experiments show that our $3P$ and $5P$ formulas had an important role in speeding up the greedy, the ternary/binary, the multi-base NAF, and the tree-based methods over the NAF method. We also establish an efficient $3P$ formula for Koblitz curves and use it to construct an improved set for the optimal pre-computation of window TNAF.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
binary elliptic curvespoint multiplicationlambda coordinatesefficient formulasDBNSMBNS
Contact author(s)
gxu4uwm @ uwm edu
History
2017-09-06: received
Short URL
https://ia.cr/2017/840
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/840,
      author = {Saud Al Musa and Guangwu Xu},
      title = {Fast Scalar Multiplication for Elliptic Curves over Binary Fields by Efficiently Computable Formulas},
      howpublished = {Cryptology ePrint Archive, Paper 2017/840},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/840}},
      url = {https://eprint.iacr.org/2017/840}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.