Paper 2012/519

Faster implementation of scalar multiplication on Koblitz curves

Diego F. Aranha, Armando Faz-Hernández, Julio López, and Francisco Rodríguez-Henríquez

Abstract

We design a state-of-the-art software implementation of field and elliptic curve arithmetic in standard Koblitz curves at the 128-bit security level. Field arithmetic is carefully crafted by using the best formulae and implementation strategies available, and the increasingly common native support to binary field arithmetic in modern desktop computing platforms. The i-th power of the Frobenius automorphism on Koblitz curves is exploited to obtain new and faster interleaved versions of the well-known $\tau$NAF scalar multiplication algorithm. The usage of the $\tau^{\lfloor m/3 \rfloor}$ and $\tau^{\lfloor m/4 \rfloor}$ maps are employed to create analogues of the 3-and 4-dimensional GLV decompositions and in general, the $\lfloor m/s \rfloor$-th power of the Frobenius automorphism is applied as an analogue of an $s$-dimensional GLV decomposition. The effectiveness of these techniques is illustrated by timing the scalar multiplication operation for fixed, random and multiple points. To our knowledge, our library was the first to compute a random point scalar multiplication in less than 10^5 clock cycles among all curves with or without endomorphisms defined over binary or prime fields. The results of our optimized implementation suggest a trade-off between speed, compliance with the published standards and side-channel protection. Finally, we estimate the performance of curve-based cryptographic protocols instantiated using the proposed techniques and compare our results to related work.

Note: Minor fixes in the Appendix.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. LATINCRYPT 2012
Contact author(s)
dfaranha @ gmail com
History
2013-12-28: last of 2 revisions
2012-09-05: received
See all versions
Short URL
https://ia.cr/2012/519
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/519,
      author = {Diego F.  Aranha and Armando Faz-Hernández and Julio López and Francisco Rodríguez-Henríquez},
      title = {Faster implementation of scalar multiplication on Koblitz curves},
      howpublished = {Cryptology ePrint Archive, Paper 2012/519},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/519}},
      url = {https://eprint.iacr.org/2012/519}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.