Extending the GHS Weil Descent Attack

S. D.  Galbraith; F.  Hess; N. P.  Smart

Paper 2001/054

Extending the GHS Weil Descent Attack

S. D. Galbraith, 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.

Metadata

Available format(s): PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: elliptic curve cryptosystems
Contact author(s): nigel @ cs bris ac uk
History: 2001-07-06: received
Short URL: https://ia.cr/2001/054
License: CC BY

BibTeX

@misc{cryptoeprint:2001/054,
      author = {S. D.  Galbraith and F.  Hess and N. P.  Smart},
      title = {Extending the {GHS} Weil Descent Attack},
      howpublished = {Cryptology {ePrint} Archive, Paper 2001/054},
      year = {2001},
      url = {https://eprint.iacr.org/2001/054}
}