Weil descent and the GHS attack
The GHS attack is the clearest example of the most dangerous shape in cryptanalysis: not a faster algorithm for your problem, but a structure-preserving map from your problem into someone else's, which was solved long ago.
- Problem
- ECDLP on E/Fqn, characteristic 2, n composite or small
- Mechanism
- Weil restriction to an abelian variety, then a covering curve
- Cost after transfer
- Subexponential, via hyperelliptic index calculus
- Affects
- Binary curves with composite extension degree; some degree-n cases with n ∈ {5, 7}
- Does not affect
- F2m with m prime and large — the standardised choice
The shape of the attack
Hyperelliptic curves of large genus are not good cryptographic groups. Adleman, DeMarrais and Huang, and later Gaudry and Enge–Gaudry, showed that index calculus works well in their Jacobians: divisors factor into prime divisors, so smoothness exists, so relations are cheap. High genus is therefore something to avoid, and nobody deploys it.
The GHS attack does not attack your elliptic curve. It constructs a hyperelliptic curve whose Jacobian contains your group, solves the discrete logarithm there, and maps the answer back. Your curve was never weak on its own terms; it was reachable from something weak.
The mechanism
Let E be defined over k = Fqn with subfield k0 = Fq. The Weil restriction of scalars W = Resk/k0(E) is an abelian variety of dimension n over k0 whose k0-points are exactly the k-points of E. No information is lost; the group is simply viewed over the smaller field.
Gaudry, Hess and Smart then find a curve C over k0 mapping into W, built in characteristic 2 from an Artin–Schreier construction applied to the curve equation. Composing the two directions gives group homomorphisms
The genus of C is the parameter that decides everything. It is controlled by the Frobenius action on the 2-torsion-related data of the curve equation, and is roughly 2m−1 or 2m−1 − 1 for a quantity m ≤ n determined by the curve. Too small and the transfer loses information; too large and the Jacobian index calculus becomes more expensive than attacking E directly. The attack works in a window, and whether a given curve falls in that window is a computable property of its coefficients.
What it actually broke
Menezes and Qu showed that the attack does not apply to F2m with m prime in the range used by the standards, which is what kept the ANSI and NIST binary curves — m = 163, 233, 283, 409, 571, all prime — out of reach. The vulnerable cases are composite m, where a genuine intermediate subfield exists.
The most-cited concrete result is Jacobson, Menezes and Stein's solution of an ECDLP over F2124 by descent to genus 31 over F24, a computation far below the cost of rho on the same curve. Later work by Gaudry (the GHS variant using isogenies and covers) and by Hess extended coverage to more curves, including some cases with n prime and small, notably n = 5 and n = 7.
The generalisation worth remembering
GHS sits in a family of transfer attacks, and that family is the right mental index:
- MOV / Frey–Rück. The Weil or Tate pairing embeds E(Fq) into Fqk×, where index calculus is subexponential. Harmless when the embedding degree k is large, fatal for supersingular curves where k ≤ 6 — and deliberately exploited in pairing-based cryptography, which is the same fact used constructively.
- Smart–Satoh–Araki. An anomalous curve, with #E(Fp) = p, lifts to the p-adics and the formal logarithm solves the ECDLP in linear time.
- Weil descent. This page: transfer to a higher-genus Jacobian over a subfield.
- Cover and decomposition attacks. Gaudry's decomposition method and the cover attacks of Diem combine descent with summation-polynomial relation search.
Each is checkable in advance from published curve data: embedding degree, trace, field structure, and the covering computation. Curve validation criteria such as those in SafeCurves or the ANSI X9.62 conditions exist to close all of them at once.
The boundary
Weil descent needs a subfield. A curve over a prime field has none, so this entire family is inapplicable to P-256, secp256k1 and Curve25519 — their exposure remains the generic bound.
The broader lesson survives the specific attack, and is the reason this page exists in a library aimed at parameter-setters: a hardness assumption is only as strong as the weakest object your instance can be mapped into, and the relevant review question is which maps out of your group are efficiently computable. Extension-field structure, small embedding degree and unusual trace are the three that have historically had answers.
Primary sources
- P. Gaudry, F. Hess and N. P. Smart, "Constructive and destructive facets of Weil descent on elliptic curves", Journal of Cryptology 15 (2002)
- A. Menezes and M. Qu, "Analysis of the Weil descent attack of Gaudry, Hess and Smart", CT-RSA 2001
- M. Jacobson, A. Menezes and A. Stein, "Solving elliptic curve discrete logarithm problems using Weil descent" (2001)
- A. Menezes, T. Okamoto and S. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field", IEEE Trans. Inf. Theory 39 (1993)
- N. P. Smart, "The discrete logarithm problem on elliptic curves of trace one", Journal of Cryptology 12 (1999)