Details:
Title  Elliptic curve discrete logarithm problem over small degree extension fields.  Author(s)  Antoine Joux, Vanessa Vitse  Type  Article in Journal  Abstract  n 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 defined over a small degree extension field 𝔽qn. In this paper, we study a variation of this index calculus method, improving the overall asymptotic complexity when n=Ω(log2q‾‾‾‾‾‾√3). In particular, we are able to successfully obtain relations on E(𝔽q5), 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 variation of Faugère’s Gröbner basis algorithm F4, which significantly speeds up the relation computation. We show how this index calculus also applies to oracleassisted resolutions of the static Diffie–Hellman problem on these elliptic curves.  Keywords  Elliptic curve, Discrete logarithm problem (DLP), Index calculus, Gröbner basis computation, Summation polynomials, Static Diffie–Hellman problem  ISSN  09332790; 14321378/e 
URL 
http://link.springer.com/article/10.1007%2Fs001450119116z 
Language  English  Journal  J. Cryptology  Volume  26  Number  1  Pages  119143  Publisher  Springer US, New York, NY  Year  2013  Edition  0  Translation 
No  Refereed 
No 
