You are looking at a specific version 20130531:063858 of this paper. See the latest version.

Paper 2013/158

Efficient and Secure Algorithms for GLV-Based Scalar Multiplication and their Implementation on GLV-GLS Curves

Armando Faz-Hernandez and Patrick Longa and Ana H. Sanchez

Abstract

We propose efficient algorithms and formulas that improve the performance of side-channel protected elliptic curve computations, with special focus on scalar multiplication exploiting the Gallant-Lambert-Vanstone (CRYPTO 2001) and Galbraith-Lin-Scott (EUROCRYPT 2009) methods. Firstly, by adapting Feng et al.'s recoding to the GLV setting, we derive new regular algorithms for variable-base scalar multiplication that offer protection against simple side-channel and timing attacks. Secondly, we propose an efficient algorithm for fixed-base scalar multiplication that is also protected against side-channel attacks by combining Feng et al.'s recoding with Lim-Lee's comb method. Thirdly, we propose an efficient technique that interleaves ARM-based and NEON-based multiprecision operations over an extension field, as typically found on GLS curves and pairing computations, to improve performance on modern ARM processors. Finally, we showcase the efficiency of the proposed techniques by implementing a state-of-the-art GLV-GLS curve in twisted Edwards form defined over GF(p^2), which supports a four dimensional decomposition of the scalar and is fully protected against timing attacks. Analysis and performance results are reported for modern x64 and ARM processors. For instance, using a precomputed table of only 512 bytes, we compute a variable-base scalar multiplication in 92,000 and 244,000 cycles on an Intel Ivy Bridge and an ARM Cortex-A15 processor (respect.); using an off-line precomputed table of 6KB, we compute a fixed-base scalar multiplication in 53,000 and 116,000 cycles (respect.); and using a precomputed table of 3KB, we compute a double scalar multiplication in 118,000 and 285,000 cycles (respect.). All of these numbers and the proposed techniques represent a significant improvement of the state-of-the-art performance of elliptic curve computations. Most notably, our techniques allow us to reduce the cost of adding protection against timing attacks in the computation of GLV-based variable-base scalar multiplication to below 10%.

Note: Major rewriting of the paper, including new side-channel protected algorithms for scalar multiplication.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Elliptic curvesscalar multiplicationside-channel protectionGLV methodGLS methodGLV-GLS curvex64 processorARM processor.
Contact author(s)
plonga @ microsoft com
History
2014-09-03: last of 6 revisions
2013-03-26: received
See all versions
Short URL
https://ia.cr/2013/158
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.