Easy scalar decompositions for efficient scalar multiplication on elliptic curves and genus 2 Jacobians

DOI10.1090/CONM/637/12753zbMATH Open1365.11081arXiv1310.5250OpenAlexW1510719509MaRDI QIDQ2811789FDOQ2811789

Authors: Benjamin Smith 

Publication date: 10 June 2016

Published in: Algorithmic Arithmetic, Geometry, and Coding Theory (Search for Journal in Brave)

Abstract: The first step in elliptic curve scalar multiplication algorithms based on scalar decompositions using efficient endomorphisms-including Gallant-Lambert-Vanstone (GLV) and Galbraith-Lin-Scott (GLS) multiplication, as well as higher-dimensional and higher-genus constructions-is to produce a short basis of a certain integer lattice involving the eigenvalues of the endomorphisms. The shorter the basis vectors, the shorter the decomposed scalar coefficients, and the faster the resulting scalar multiplication. Typically, knowledge of the eigenvalues allows us to write down a long basis, which we then reduce using the Euclidean algorithm, Gauss reduction, LLL, or even a more specialized algorithm. In this work, we use elementary facts about quadratic rings to immediately write down a short basis of the lattice for the GLV, GLS, GLV+GLS, and Q-curve constructions on elliptic curves, and for genus 2 real multiplication constructions. We do not pretend that this represents a significant optimization in scalar multiplication, since the lattice reduction step is always an offline precomputation---but it does give a better insight into the structure of scalar decompositions. In any case, it is always more convenient to use a ready-made short basis than it is to compute a new one.

Full work available at URL: https://arxiv.org/abs/1310.5250

Recommendations

• The Gallant-Lambert-Vanstone decomposition revisited
• Constructing elliptic curves for the GLV method with low-cost decomposition
• Ready-made short basis for GLV+GLS on high degree twisted curves
• scientific article; zbMATH DE number 1951601
• Some techniques for faster scalar multiplication on GLS curves

zbMATH Keywords

elliptic curvesscalar multiplicationtwo-dimensional decompositions

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Cited In (7)

• Title not available (Why is that?)
• Ready-made short basis for GLV+GLS on high degree twisted curves
• Constructing elliptic curves for the GLV method with low-cost decomposition
• The \(\mathbb Q\)-curve construction for endomorphism-accelerated elliptic curves
• Privately outsourcing exponentiation to a single server: cryptanalysis and optimal constructions
• A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level
• On Modular Decomposition of Integers

This page was built for publication: Easy scalar decompositions for efficient scalar multiplication on elliptic curves and genus 2 Jacobians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811789)