Extending the GHS Weil descent attack

Steven Galbraith; Florian Hess; Nigel Smart

Extending the GHS Weil descent attack

Steven Galbraith, Florian Hess, Nigel Smart

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 contribution	Extending the GHS Weil descent attack
Original language	English
Title of host publication	Advances in Cryptology - EUROCRYPT 2002
Publisher	Springer Berlin Heidelberg
Pages	29 - 44
Number of pages	16
Volume	2332
Publication status	Published - 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

Access to Document

http://www.springerlink.com/content/gd50gualuk6tktrc/?p=8a5b7a99077e4356916ef4a969edffa5&pi=2

Cite this

@inproceedings{f7d6e0c6ed99468c9f143b1d3964841d,

title = "Extending the GHS Weil descent attack",

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. ",

author = "Steven Galbraith and Florian Hess and Nigel Smart",

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",

year = "2002",

month = may,

language = "English",

volume = "2332",

pages = "29 -- 44",

booktitle = "Advances in Cryptology - EUROCRYPT 2002",

publisher = "Springer Berlin Heidelberg",

address = "Germany",

}

TY - GEN

T1 - Extending the GHS Weil descent attack

AU - Galbraith, Steven

AU - Hess, Florian

AU - Smart, Nigel

N1 - 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

PY - 2002/5

Y1 - 2002/5

N2 - 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.

AB - 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.

M3 - Conference Contribution (Conference Proceeding)

VL - 2332

SP - 29

EP - 44

BT - Advances in Cryptology - EUROCRYPT 2002

PB - Springer Berlin Heidelberg

ER -

Extending the GHS Weil descent attack

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this