Cryptology ePrint Archive: Report 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%.

Category / Keywords: Elliptic curves, scalar multiplication, side-channel protection, GLV method, GLS method, GLV-GLS curve, x64 processor, ARM processor.

Date: received 15 Mar 2013, last revised 31 May 2013

Contact author: plonga at microsoft com

Available format(s): PDF | BibTeX Citation

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

Version: 20130531:063858 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]