**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)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]