Extending the GHS Weil descent attack

Steven Galbraith, Florian Hess, Nigel Smart

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

56 Citations (Scopus)

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 applies to fields of composite degree over $\F_2$. The principle behind the extended attack is to use isogenies to find an 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 isogenous curve. A further 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 show that a larger proportion than previously thought of elliptic curves over $\F_2^155$ should be considered weak.
Translated title of the contributionExtending the GHS Weil descent attack
Original languageEnglish
Title of host publicationAdvances in Cryptology - EUROCRYPT 2002
PublisherSpringer Berlin Heidelberg
Pages29 - 44
Number of pages16
Volume2332
Publication statusPublished - May 2002

Bibliographical note

Editors: Knudsen, L
ISBN: 3540435530
Publisher: Springer
Name and Venue of Conference: Advances in Cryptology - EUROCRYPT 2002: International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, 28 April 28 - 2 May
Other: http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=1000621

Fingerprint

Dive into the research topics of 'Extending the GHS Weil descent attack'. Together they form a unique fingerprint.

Cite this