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 cryptographymultibase representationscalar multiplication
Contact author(s)
luaming @ msn com
History
2011-10-25: received
Short URL
https://ia.cr/2011/569
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2011/569}},
      url = {https://eprint.iacr.org/2011/569}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.