Solving elliptic curve discrete logarithm problems using Weil descent

Authors Andreas Stein, Michael J. Jacobson jun., Alfred Menezes

Publication date 25 February 2003

Published in Journal of the Ramanujan Mathematical Society (Search for Journal in Brave)

elliptic curve discrete logarithm problem index-calculus Weil descent

Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Review text

This paper in the authors' words \`\` provides the first cryptographically interesting instance of the elliptic curve discrete logarithm problem which resists all previously known attacks, but which can be solved with modest computer resources using the Weil descent attack.NEWLINENEWLINENEWLINEThe descent of Weil, like a tool to translate the discrete logarithm problem in an elliptic curve over a finite field \(\mathbb{F}_{q^n}\) to the discrete logarithm problem in an Abelian variety over \(\mathbb{F}_q\), was initially proposed by \textit{G. Frey} [Proceedings fifth international conference on finite fields and applications, Springer, 128-161 (2001; Zbl 1015.94545)] and later on developed by \textit{P. Gaudry, F. Hess} and \textit{N. Smart} (the GHS attack) [J. Cryptology 15, 19-46 (2001; Zbl 0996.94036)], who reduced it to the discrete logarithm problem on the Jacobian of a hyperelliptic curve over \(\mathbb{F}_q\) and outlined the possibilities of a cryptanalytic attack to this last problem. NEWLINENEWLINENEWLINEThe first introductory sections recall the theory of hyperelliptic curves (Section 2), the Weil descent attack (Section 3) and the method of index-calculus in hyperelliptic curves (Section 4).NEWLINENEWLINENEWLINEIn Section 5 the authors provide details of their own implementation of the Enge-Gaudry index-calculus method [\textit{A. Enge} and \textit{P. Gaudry}, Acta Arith. 102, 83-103 (2002; Zbl 1028.11079)], for solving the discrete logarithm problem in the Jacobian of genus 31 hyperelliptic curves over \(\mathbb{F}_q\), for \(q=4,8,16,32\).NEWLINENEWLINENEWLINEFinally Section 6 discuss the cryptographic implications, showing that the ECDLP in a particular elliptic curve over \(\mathbb{F}_{2^{155}}\), intractable using previous attacks, can be reduced, using the GHS techniques, to instances of the discrete logarithm problem in genus 31 hyperelliptic curves over \(\mathbb{F}_{2^5}\), which can be solved with the index-calculus methods of Section 5.NEWLINENEWLINENEWLINEThe authors stress, however, that such an attack could be successful only with a minimum proportion (\(2^{32}\) out of the \(2^{156} \)) of elliptic curves on \(F_{2^{155}}\). But it should be pointed out that \textit{S. D. Galbraith, F. Hess} and \textit{N. P. Smart} [Eurocrypt 2002{} Springer Lect. Notes Comput. Sci. 2332, 29-44 (2002)], have later extended the GHS attack to a much larger class of elliptic curves (in the example of Jacobson, Menezes and Stein to around \(2^{104}\) curves) NEWLINENEWLINENEWLINEThey also point out a result of \textit{A. Menezes} and \textit{M. Qu} [Topics in Cryptology 2001, Springer, Lect. Notes Comput. Sci. 2020, 308-318 (2001; Zbl 0985.94029)] that shows that the GHS attack is inefficient over fields \(\mathbb{F}_{2^m}\), with \(m\) prime and \(m\in [160,600]\).

Recommendations

Cited in

(29)

This page was built for publication: Solving elliptic curve discrete logarithm problems using Weil descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2765411)