Four-dimensional Gallant-Lambert-Vanstone scalar multiplication

Patrick Longa, Francesco Sica

Research output: Contribution to journalArticle

15 Citations (Scopus)

Abstract

The GLV method of Gallant, Lambert, and Vanstone (CRYPTO 2001) computes any multiple kP of a point P of prime order n lying on an elliptic curve with a low-degree endomorphism Φ (called GLV curve) over Fp kP = k 1P+ k2Φ(P) with max {|k1|,|k2|} ≤ C1 √n for some explicit constant C1>0. Recently, Galbraith, Lin, and Scott (EUROCRYPT 2009) extended this method to all curves over Fp2 which are twists of curves defined over F p2. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over Fp2, a four-dimensional decomposition together with fast endomorphisms Φ,Ψ over Fp2 acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k∈[1,n] given by kP=k1P+ k2Φ(P)+ k3Ψ(P) + k4ΨΦ(P) with maxi |ki|)< C2, n1/4 for some explicit C2>0. Remarkably, taking the best C1,C 2, we obtain C2/C1<412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV-GLS approach supports a scalar multiplication that runs up to 1.5 times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of scalar multiplication on elliptic curves over large prime characteristic fields for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.

Original languageEnglish
Pages (from-to)248-283
Number of pages36
JournalJournal of Cryptology
Volume27
Issue number2
DOIs
Publication statusPublished - Apr 2014

Keywords

  • Elliptic curves
  • GLV-GLS method
  • Multicore computation
  • Scalar multiplication
  • Side-channel protection
  • Twisted Edwards curve

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Four-dimensional Gallant-Lambert-Vanstone scalar multiplication'. Together they form a unique fingerprint.

  • Cite this