Constructive and destructive facets of Weil descent on elliptic curves
type: Item
instance of: scholarly article
title: Constructive and destructive facets of Weil descent on elliptic curves
zbMATH Open document ID: 0996.94036
published in: Journal of Cryptology
publication date: 2002-05-21T00:00:00Z
full work available at URL: weildesc vZ.pdf
review text: 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 ext…
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 11G07
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 1743184
zbMATH Keywords: Weil descent
zbMATH Keywords: discrete logarithm problem
zbMATH Keywords: elliptic curve
zbMATH Keywords: Jacobian
zbMATH Keywords: hyperelliptic curve
zbMATH Keywords: hyperelliptic cryptosystems
zbMATH Keywords: cryptanalytic attacks
author: Pierrick Gaudry
author: Florian Hess
author: N. P. Smart
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
OpenAlex ID: W2084836129
cites work: Q4847910
cites work: Q4692374
cites work: Q4265362
cites work: Computing in the Jacobian of a Hyperelliptic Curve
cites work: Q5810622
cites work: A general framework for subexponential discrete logarithm algorithms
cites work: A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
cites work: Q4945368
cites work: Q3374896
cites work: Q4509883
cites work: Q3216750
cites work: Computing discrete logarithms in real quadratic congruence function fields of large genus
cites work: Q4254917
cites work: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
cites work: Q3710637
cites work: Q4250782
cites work: Algebraic function fields and codes
DOI: 10.1007/S00145-001-0011-X
description: scientific article; zbMATH DE number 1743184