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

Saud Al Musa; Guangwu Xu

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 $3 P$ formula in $λ$ -projective coordinates and $5 P$ formula in both affine and $λ$ -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 $3 P$ and $5 P$ 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 $3 P$ 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 curves point multiplication lambda coordinates efficient formulas DBNS MBNS
Contact author(s): gxu4uwm @ uwm edu
History: 2017-09-06: received
Short URL: https://ia.cr/2017/840
License: 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},
      url = {https://eprint.iacr.org/2017/840}
}