Abstract
A finite field K is said to be weak for elliptic curve cryptography if all instances of the discrete logarithm problem for all elliptic curves over K can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. By considering the GHS Weil descent attack, it was previously shown that characteristic two finite fields 
are weak. In this paper, we examine characteristic two finite fields 
for weakness under Hess' generalization of the GHS attack. We show that the fields 
are potentially partially weak in the sense that any instance of the discrete logarithm problem for half of all elliptic curves over , namely those curves E for which 
is divisible by 4, can likely be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We also show that the fields 
are partially weak, that the fields 
are potentially weak, and that the fields 
are potentially partially weak. Finally, we argue that the other fields 
where N is not divisible by 3, 5, 6, 7 or 8, are not weak under Hess' generalized GHS attack.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Adleman, L., DeMarrais, J., Huang, M.: A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields. Algorithmic Number Theory, Lecture Notes in Computer Science, 877, 28–40 (1994)
Enge, A., Gaudry, P.: A general framework for subexponential discrete logarithm algorithms. Acta Arithmetica 102, 83–103 (2002)
Frey, G.: Applications of arithmetical geometry to cryptographic constructions. Proceedings of the Fifth International Conference on Finite Fields and Applications, Springer-Verlag, 2001, pp. 128–161
Frey, G., Rück, H.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation 62, 865–874 (1994)
Galbraith, S.: Constructing isogenies between elliptic curves over finite fields. LMS Journal of Computation and Mathematics 2, 118–138 (1999)
Galbraith, S., Hess, F., Smart, N.: Extending the GHS Weil descent attack. Advances in Cryptology–-EUROCRYPT 2002 Lecture Notes in Computer Science, 2332, 29–44 (2002)
Gaudry, P.: An algorithm for solving the discrete log problem in hyperelliptic curves. Advances in Cryptology—EUROCRYPT 2000, Lecture Notes in Computer Science, 1807, 19–34 (2000)
Gaudry, P.: Index calculus for abelian varieties and the elliptic curve discrete logarithm problem. Cryptology ePrint Archive: Report 2004/073, 2004 Available from http://eprint.iacr.org/2004/073/
Gaudry, P., Hess, F., Smart, N.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptol. 15, 19–46 (2002)
Gaudry, P., Thériault, N., Thomé, E.: A double large prime variation for small genus hyperelliptic index calculus. Cryptology ePrint Archive: Report 2004/153, 2004 Available from http://eprint.iacr.org/2004/153/
Hess, F.: Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symbol. Comput. 33, 425–445 (2002)
Hess, F.: Computing relations in divisor class groups of algebraic curves over finite fields. preprint, 2003
Hess, F.: Generalising the GHS attack on the elliptic curve discrete logarithm problem. LMS J. Comput. Math. 7, 167–192 (2004)
Hess, F.: Weil descent attacks. In: Blake, I., Seroussi, G., Smart, N. (eds.) Advances in elliptic curve cryptography, Cambridge University Press, 2005
Kohel, D.: Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California, Berkeley, 1996
Maurer, M., Menezes, A., Teske, E.: Analysis of the GHS Weil descent attack on the ECDLP over characteristic two finite fields of composite degree. LMS J. Comput. Math. 5, 127–174 (2002)
Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inform. Theory 39, 1639–1646 (1993)
Menezes, A., Qu, M.: Analysis of the weil descent attack of gaudry, hess and smart. Topics in Cryptology—CT-RSA 2001, Lecture Notes in Computer Science, 2020, 308–318 (2001)
Menezes, A., Teske, E., Weng, A.: Weak fields for ECC. Topics in Cryptology—CT-RSA 2004, Lecture Notes in Computer Science, 2964, 366–386 (2004)
van Oorschot, P., Wiener, M.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12, 1–28 (1999)
Pollard, J.: Monte Carlo methods for index computation mod p. Math. Comput. 32, 918–924 (1978)
Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Commentarii Mathematici Universitatis Sancti Pauli 47, 81–92 (1998)
Semaev, I.: Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Math. Comput. 67, 353–356 (1998)
Smart, N.: The discrete logarithm problem on elliptic curves of trace one. J. Cryptol. 12, 193–196 (1999)
Teske, E.: On random walks for Pollard's rho method. Math. Comput. 70, 809–825 (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Menezes, A., Teske, E. Cryptographic implications of Hess' generalized GHS attack. AAECC 16, 439–460 (2006). https://doi.org/10.1007/s00200-005-0186-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-005-0186-8