Following previous ideas of G. Frey [ECC ’98, Waterloo (1998)] and S. D. Galbraith and N. P. Smart [7th IMA Conference, Lect. Notes Comput. Sci. 1746, 191-200 (1999; Zbl 0981.94025)] the authors use the Weil descent technique to translate the discrete logarithm problem on an elliptic curve \(E\) over a finite field \(F_{q^n}\) to the discrete logarithm problem on the Jacobian of a hyperelliptic curve \(C\), built by intersecting \(n-1\) hyperplanes associated to the Weil restriction of \(E\) with an \(n\)-dimensional variety over \(F_q\).
The paper studies the case \(q=2^r\), \(r>1\) (the characteristic 2 assumption is crucial in the proof). Nevertheless, at the end of the paper, the authors discuss the situation in the cases \(q=2\), \(n\) prime (the common case in cryptography) and \(q\) odd.
As the title suggests, the paper studies two antagonistic applications of this technique: design of hyperelliptic cryptosystems and cryptanalytic attacks on the original elliptic cryptosystem. The cryptographic implications of the second possibility are obvious, however the authors stress that their method does “not appear to be a threat to standards compliant elliptic curve systems in the real world”.
The GHS attack has been further analysed in other papers. For instance M. Jacobson, A. Menezes and A. Stein [J. Ramanujan Math. Soc. 16, 231-260 (2001; Zbl 1017.11030)] show, for the particular case \(q= 2^5\), \(n=31\), that the method could be successful only with \(2^{33}\) out of the \(2^{156}\) total isomorphism classes of elliptic curves. However S. D. Galbraith, F. Hess and N. P. Smart [EUROCRYPT 2002, Lect. Notes Comput. Sci. 2332, 29-44 (2002)] extend the GHS attack to a much larger class of elliptic curves (in the example of Jacobson, Menezes and Stein to around \(2^{104}\) curves). This seems to strengthen the idea of the cryptographic weakness of the elliptic curves over composite extension fields.