Cryptology ePrint Archive: Report 2001/084

Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree

Markus Maurer and Alfred Menezes and Edlyn Teske

Abstract: In this paper, we analyze the Gaudry-Hess-Smart (GHS) Weil descent attack on the elliptic curve discrete logarithm problem (ECDLP) for elliptic curves defined over characteristic two finite fields of composite extension degree. For each such field $F_{2^N}$, $N \in [100,600]$, we identify elliptic curve parameters such that (i) there should exist a cryptographically interesting elliptic curve $E$ over $F_{2^N}$ with these parameters; and (ii) the GHS attack is more efficient for solving the ECDLP in $E(F_{2^N})$ than for solving the ECDLP on any other cryptographically interesting elliptic curve over $F_{2^N}$. We examine the feasibility of the GHS attack on the specific elliptic curves over $F_{2^{176}}$, $F_{2^{208}}$, $F_{2^{272}}$, $F_{2^{304}}$, and $F_{2^{368}}$ that are provided as examples inthe ANSI X9.62 standard for the elliptic curve signature scheme ECDSA. Finally, we provide several concrete instances of the ECDLP over $F_{2^N}$, $N$ composite, of increasing difficulty which resist all previously known attacks but which are within reach of the GHS attack.

Category / Keywords: public-key cryptography / elliptic curve discrete logarithm problem, Weil descent attack

Publication Info: Full version of a paper to appear in the Indocrypt 2001 proceedings

Date: received 12 Oct 2001

Contact author: ajmeneze at uwaterloo ca

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20011012:162316 (All versions of this report)

Short URL: ia.cr/2001/084

Discussion forum: Show discussion | Start new discussion