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 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 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 runs in constant time, i.e., it is fully protected against timing attacks. For instance, using a precomputed table of only 512 bytes, we compute a variable-base scalar multiplication in 92,000 cycles on an Intel Ivy Bridge processor and in 244,000 cycles on an ARM Cortex-A15 processor. Our benchmark results and the proposed techniques contribute to the 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 GLV-based variable-base scalar multiplication computation to below 10%.

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

Original Publication (with minor differences): CT-RSA 2014

Date: received 15 Mar 2013, last revised 19 Feb 2014

Contact author: plonga at microsoft com

Available format(s): PDF | BibTeX Citation

Note: Corrected a typo in Table 2 when citing [18].

Version: 20140219:093744 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]