Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction

# Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction

Sep 1, 2011·,,,,,·
0 min read

Jonathan Taverne

Armando Faz-Hernández

Diego F. Aranha

Francisco Rodríguez-Henríquez

Darrel Hankerson

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. The algorithms presented in this work were implemented on Westmere and Sandy Bridge processors, the latest generation Intel microarchitectures.

Type

Publication

*Journal of Cryptographic Engineering*

### Related

- Implementación multinúcleo de la multiplicación escalar en curvas de Koblitz
- Faster Implementation of Scalar Multiplication on Koblitz Curves
- Efficient and Secure Algorithms for GLV-Based Scalar Multiplication and Their Implementation on GLV-GLS Curves
- Fast Implementation of Curve25519 Using AVX2
- Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves (extended version)