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.