Cryptographic implications of Hess' generalized GHS attack

摘要

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