Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem - Archive ouverte HAL Access content directly
Journal Articles Journal of Symbolic Computation Year : 2009

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

(1, 2, 3)
1
2
3

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)).
Fichier principal
Vignette du fichier
indexcalc.pdf (201.2 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00337631 , version 1 (07-11-2008)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More