Cryptology ePrint Archive: Report 2013/158

Keep Calm and Stay with One (and p>3)

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

Abstract: We demonstrate the high-speed computation of core elliptic curve operations with full protection against timing-type side-channel attacks. We use a state-of-the-art GLV-GLS curve in twisted Edwards form defined over a quadratic extension field of large prime characteristic, which supports a four dimensional decomposition of the scalar. We present highly optimized algorithms and formulas for speeding up the different arithmetic layers, including techniques especially suitable for high-speed, side-channel protected computation on GLV-based implementations. Analysis and performance results are reported for modern x64 and ARM processors. For instance, on an Intel Ivy Bridge processor we compute a variable-base scalar multiplication in 94,000 cycles, a fixed-base scalar multiplication in 53,000 cycles using a table of 6KB, and a double scalar multiplication in 118,000 cycles using a table of 3KB. Similarly, on an ARM Cortex-A15 processor we compute a variable-base scalar multiplication in 244,000 cycles, a fixed-base scalar multiplication in 116,000 cycles (table of 6KB), and a double scalar multiplication in 285,000 cycles (table of 3KB). All these numbers and the proposed techniques represent a significant improvement of the state-of-the-art performance of elliptic curve computations. Most remarkably, our optimizations allow us to reduce the cost of adding protection against timing attacks in the computation of variable-base scalar multiplication to around or below 10%.

Category / Keywords: implementation / Elliptic curves, scalar multiplication, GLV-GLS curves, twisted Edwards form, side-channel protection, prime fields.

Date: received 15 Mar 2013, last revised 16 Mar 2013

Contact author: plonga at microsoft com

Available formats: PDF | BibTeX Citation

Version: 20130326:134803 (All versions of this report)

Discussion forum: Show discussion | Start new discussion