Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem

Pierrick Gaudry 1, 2, 3
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
3 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties of small dimension. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve an elliptic curve discrete logarithm problem defined over GF(q^3) in heuristic asymptotic running time O~(q^(4/3)); and an elliptic problem over GF(q^4) or a genus 2 problem over GF(q^2) in heuristic asymptotic running time O~(q^(3/2)).
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2009, 44 (12), pp.1690-1702. 〈10.1016/j.jsc.2008.08.005〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00337631
Contributeur : Pierrick Gaudry <>
Soumis le : vendredi 7 novembre 2008 - 15:11:17
Dernière modification le : jeudi 10 mai 2018 - 02:06:15
Document(s) archivé(s) le : lundi 7 juin 2010 - 22:48:39

Fichier

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

Identifiants

Collections

Citation

Pierrick Gaudry. Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. Journal of Symbolic Computation, Elsevier, 2009, 44 (12), pp.1690-1702. 〈10.1016/j.jsc.2008.08.005〉. 〈inria-00337631〉

Partager

Métriques

Consultations de la notice

512

Téléchargements de fichiers

434