Analysis of the Hamming Weight of the Extended wmbNAF

Ming Li; Ali Miri; Daming Zhu

Paper 2011/569

Analysis of the Hamming Weight of the Extended wmbNAF

Ming Li, Ali Miri, and Daming Zhu

Abstract

Scalar multiplication is an important operation in elliptic curve cryptosystems(ECC). The algorithms for computing scalar multiplication are mostly based on the binary expansions of scalars, such as the non-adjacent form (NAF) and wNAF(sliding window method). Representing scalars using more bases can speed up the scalar multiplication, such as mbNAF, wmbNAF and extended wmbNAF, which was proposed by Longa and Miri in 2008. In this paper, we give a formal analysis of the Hamming weight of the extended wmbNAF method for scalar multiplication on general elliptic curves over large prime fields. Then the cost of this method is compared with NAF and other double-base methods. The analysis shows that we obtain the most efficient algorithm when using (2; 3; 5)NAF_{1;1;0}, which is 9:0% faster than the NAF method without extra storage requirement. Moreover, the recoding algorithm of the extended wmbNAF method is just as simple and fast as that of the NAF method.

Note: It has been submitted to IPL in 2010.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: elliptic curve cryptography multibase representation scalar multiplication
Contact author(s): luaming @ msn com
History: 2011-10-25: received
Short URL: https://ia.cr/2011/569
License: CC BY

BibTeX

@misc{cryptoeprint:2011/569,
      author = {Ming Li and Ali Miri and Daming Zhu},
      title = {Analysis of the Hamming Weight of the Extended {wmbNAF}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/569},
      year = {2011},
      url = {https://eprint.iacr.org/2011/569}
}