Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields
Antoine Joux, Vanessa Vitse · 2010
In 2008 and 2009, Gaudry and Diem proposed an index calculus method for the resolution of the discrete logarithm on the group of points of an elliptic curve dened over a small degree extension eld Fqn. In this paper, we study a variation of this index calculus method, improving the overall asymptotic complexity when logq cn 3 . In particular, we are able to successfully obtain relations on E(Fp5), whereas the more expensive computational complexity of Gaudry and Diem's initial algorithm makes it impractical in this case. An important ingredient of this result is a new variation of Faug ere's Grobner basis algorithm F4, which signicantly speeds up the relation computation and might be of independent interest. As an application, we show how this index calculus leads to a practical example of an oracle-assisted resolution of the elliptic curve static Die-Hellman problem over a nite eld on 130 bits, which is faster than birthday-based discrete logarithm computations on the same curve.