Paper 2013/131

Two is the fastest prime

Thomaz Oliveira and Julio López and Diego F. Aranha and Francisco Rodríguez-Henríquez

Abstract

In this work, we present new arithmetic formulas based on the $\lambda$ point representation that lead to the efficient computation of the scalar multiplication operation over binary elliptic curves. A software implementation of our formulas applied to a binary Galbraith-Lin-Scott elliptic curve defined over the field $\mathbb{F}_{2^{254}}$ allows us to achieve speed records for pro\-tec\-ted/\-un\-pro\-tec\-ted single/multi-core random-point elliptic curve scalar multiplication at the 127-bit security level. When executed on a Sandy Bridge 3.4GHz Intel Xeon processor, our software is able to compute a single/multi-core unprotected scalar multiplication in $69,500$ and $47,900$ clock cycles, respectively; and a protected single-core scalar multiplication in $114,800$ cycles. These numbers improve by around 2\% and 46\% on the newer Ivy Bridge and Haswell platforms, respectively, achieving in the latter a protected random-point scalar multiplication in 60,000 clock cycles.