Paper 2004/235

Cryptographic Implications of Hess' Generalized GHS Attack

Alfred Menezes and Edlyn Teske

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 GF(q^5) are weak. In this paper, we examine characteristic two finite fields GF(q^n) for weakness under Hess' generalization of the GHS attack. We show that the fields GF(q^7) are potentially partially weak in the sense that any instance of the discrete logarithm problem for half of all elliptic curves over GF(q^7), namely those curves E for which #E 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 GF(q^3) are partially weak, that the fields GF(q^6) are potentially weak, and that the fields GF(q^8) are potentially partially weak. Finally, we argue that the other fields GF(2^N) where N is not divisible by 3, 5, 6, 7 or 8, are not weak under Hess' generalized GHS attack.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
ajmeneze @ uwaterloo ca
History
2004-09-16: revised
2004-09-16: received
See all versions
Short URL
https://ia.cr/2004/235
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/235,
      author = {Alfred Menezes and Edlyn Teske},
      title = {Cryptographic Implications of Hess' Generalized GHS Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2004/235},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/235}},
      url = {https://eprint.iacr.org/2004/235}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.