Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / binary elliptic curves, point multiplication, lambda coordinates, efficient formulas, DBNS, MBNS

Date: received 31 Aug 2017

Contact author: gxu4uwm at uwm edu

Available format(s): PDF | BibTeX Citation

Version: 20170906:175832 (All versions of this report)

Short URL: ia.cr/2017/840

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]