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

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.
Type de document :
Article dans une revue
Contemporary mathematics, American Mathematical Society, 2015, Algorithmic Arithmetic, Geometry, and Coding Theory, 637, pp.15
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00874925
Contributeur : Benjamin Smith <>
Soumis le : samedi 19 octobre 2013 - 12:00:34
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : lundi 20 janvier 2014 - 04:25:24

Fichiers

easy.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

  • HAL Id : hal-00874925, version 1
  • ARXIV : 1310.5250

Citation

Benjamin Smith. Easy scalar decompositions for efficient scalar multiplication on elliptic curves and genus 2 Jacobians. Contemporary mathematics, American Mathematical Society, 2015, Algorithmic Arithmetic, Geometry, and Coding Theory, 637, pp.15. 〈hal-00874925〉

Partager

Métriques

Consultations de la notice

565

Téléchargements de fichiers

330