CryptoDB
Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree
| Authors: | |
|---|---|
| Download: | |
| 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
}