International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptographic Implications of Hess' Generalized GHS Attack

Authors:
Alfred Menezes
Edlyn Teske
Download:
URL: http://eprint.iacr.org/2004/235
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12205,
  title={Cryptographic Implications of Hess' Generalized GHS Attack},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/2004/235},
  note={ ajmeneze@uwaterloo.ca 12677 received 13 Sep 2004, last revised 16 Sep 2004},
  author={Alfred Menezes and Edlyn Teske},
  year=2004
}