Paper 2001/084

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

Markus Maurer, Alfred Menezes, and Edlyn Teske


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Full version of a paper to appear in the Indocrypt 2001 proceedings
elliptic curve discrete logarithm problemWeil descent attack
Contact author(s)
ajmeneze @ uwaterloo ca
2001-10-12: received
Short URL
Creative Commons Attribution


      author = {Markus Maurer and Alfred Menezes and Edlyn Teske},
      title = {Analysis of the {GHS} Weil Descent Attack on the {ECDLP} over Characteristic Two Finite Fields of Composite Degree},
      howpublished = {Cryptology ePrint Archive, Paper 2001/084},
      year = {2001},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.