Constructive and destructive facets of Weil descent on elliptic curves
Following previous ideas of \textit{G. Frey} [ECC '98, Waterloo (1998)] and \textit{S. D. Galbraith} and \textit{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 \textit{M. Jacobson}, \textit{A. Menezes} and \textit{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 \textit{S. D. Galbraith}, \textit{F. Hess} and \textit{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.
scientific article; zbMATH DE number 1743184
scientific article