Two is the fastest prime: lambda coordinates for binary elliptic curves

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

Paper 2013/131

Two is the fastest prime: lambda coordinates for binary elliptic curves

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

Abstract

In this work, we present new arithmetic formulas for a projective version of the affine point representation $(x, x + y / x),$ for $x \neq 0,$ which leads to an 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 $F_{2^{254}}$ allows us to achieve speed records for protected/unprotected 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 are improved 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.

Note: Extended version of CHES 2013 to appear in JCEN.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Journal of Cryptographic Engineering
DOI: 10.1007/s13389-013-0064-4
Keywords: elliptic curve cryptography GLS curves scalar multiplication
Contact author(s): francisco @ cs cinvestav mx
History: 2014-01-31: last of 10 revisions; 2013-03-07: received; See all versions
Short URL: https://ia.cr/2013/131
License: CC BY

BibTeX

@misc{cryptoeprint:2013/131,
      author = {Thomaz Oliveira and Julio López and Diego F.  Aranha and Francisco Rodríguez-Henríquez},
      title = {Two is the fastest prime: lambda coordinates for binary elliptic curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/131},
      year = {2013},
      doi = {10.1007/s13389-013-0064-4},
      url = {https://eprint.iacr.org/2013/131}
}