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

Category / Keywords: elliptic curve cryptography, GLS curves, scalar multiplication

Original Publication (with major differences): IACR-CHES-2013

Date: received 5 Mar 2013, last revised 4 Nov 2013

Contact author: francisco at cs cinvestav mx

Available format(s): PDF | BibTeX Citation

Version: 20131105:053049 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]