International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Markus Maurer
Alfred Menezes
Edlyn Teske
Download:
URL: http://eprint.iacr.org/2001/084
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2001-11496,
  title={Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / elliptic curve discrete logarithm problem, Weil descent attack},
  url={http://eprint.iacr.org/2001/084},
  note={Full version of a paper to appear in the Indocrypt 2001 proceedings ajmeneze@uwaterloo.ca 11607 received 12 Oct 2001},
  author={Markus Maurer and Alfred Menezes and Edlyn Teske},
  year=2001
}