Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem |
| |
Authors: | Pierrick Gaudry |
| |
Affiliation: | aLIX - École polytechnique, Route de Saclay, 91128 Palaiseau, France;bLORIA, Campus Scientifique, BP 239, 54506 Vandoeuvre-Lès-Nancy, France |
| |
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 in heuristic asymptotic running time ; and an elliptic problem over or a genus 2 problem over in heuristic asymptotic running time . |
| |
Keywords: | Discrete logarithm problem Elliptic curve Index calculus Weil descent |
本文献已被 ScienceDirect 等数据库收录! |
|