Paper 2011/170

Software implementation of binary elliptic curves: impact of the carry-less multiplier on scalar multiplication

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

Abstract

The availability of a new carry-less multiplication instruction in the latest Intel desktop processors significantly accelerates multiplication in binary fields and hence presents the opportunity for reevaluating algorithms for binary field arithmetic and scalar multiplication over elliptic curves. We describe how to best employ this instruction in field multiplication and the effect on performance of doubling and halving operations. Alternate strategies for implementing inversion and half-trace are examined to restore most of their competitiveness relative to the new multiplier. These improvements in field arithmetic are complemented by a study on serial and parallel approaches for Koblitz and random curves, where parallelization strategies are implemented and compared. The contributions are illustrated with experimental results improving the state-of-the-art performance of halving and doubling-based scalar multiplication on NIST curves at the 112- and 192-bit security levels, and a new speed record for side-channel resistant scalar multiplication in a random curve at the 128-bit security level.

Note: Fix confusion in terminology between binary curves CURVE2251 ad BBE251.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Elliptic curve cryptographyfinite field arithmeticparallel algorithmefficient software implementation
Contact author(s)
francisco @ cs cinvestav mx
History
2019-03-10: last of 4 revisions
2011-04-04: received
See all versions
Short URL
https://ia.cr/2011/170
License
Creative Commons Attribution
CC BY

BibTeX

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