Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleIndex calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
Author(s) Pierrick Gaudry
TypeArticle in Journal
AbstractWe 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 F q 3 in heuristic asymptotic running time O ̃ ( q^4 / 3 ) ; and an elliptic problem over F q 4 or a genus 2 problem over F q 2 in heuristic asymptotic running time O ̃ ( q^3 / 2 ) .
KeywordsDiscrete logarithm problem, Elliptic curve, Index calculus, Weil descent
URL http://www.sciencedirect.com/science/article/pii/S074771710800182X
JournalJournal of Symbolic Computation
Pages1690 - 1702
NoteGröbner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics
Translation No
Refereed No