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


TitleElliptic curve discrete logarithm problem over small degree extension fields.
Author(s) Antoine Joux, Vanessa Vitse
TypeArticle in Journal
Abstractn 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 oracle-assisted resolutions of the static Diffie–Hellman problem on these elliptic curves.
KeywordsElliptic curve, Discrete logarithm problem (DLP), Index calculus, Gröbner basis computation, Summation polynomials, Static Diffie–Hellman problem
ISSN0933-2790; 1432-1378/e
URL http://link.springer.com/article/10.1007%2Fs00145-011-9116-z
JournalJ. Cryptology
PublisherSpringer US, New York, NY
Translation No
Refereed No