**Extending the GHS Weil Descent Attack**

*S.D. Galbraith and F. Hess and N.P. Smart*

**Abstract: **In this paper we extend the Weil descent attack
due to Gaudry, Hess and Smart (GHS) to
a much larger class of elliptic curves.
This extended attack still only works for fields of composite
degree over $\F_2$.
The principle behind the extended attack is to use
isogenies to
find a new elliptic curve for which the GHS attack is
effective.
The discrete logarithm problem on the target curve
can be transformed into a discrete logarithm problem
on the new isogenous curve.
One contribution of the paper is to give
an improvement to an algorithm of Galbraith
for constructing isogenies between elliptic curves,
and this is of independent interest in
elliptic curve cryptography.
We conclude that fields of the form $\F_{q^7}$ should be
considered weaker from a cryptographic standpoint than
other fields.
In addition we show that a larger proportion than previously
thought of elliptic curves over $\F_{2^{155}}$ should be
considered weak.

**Category / Keywords: **public-key cryptography / elliptic curve cryptosystems

**Date: **received 6 Jul 2001

**Contact author: **nigel at cs bris ac uk

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

**Version: **20010706:173325 (All versions of this report)

**Short URL: **ia.cr/2001/054

[ Cryptology ePrint archive ]