Analysis For GHS Attack

In the year2001, P. Gaudry，F. Hess and N. P. Smart used the idea from G. Fraygive the algorithm GHS[1]. They reduced the ECDLP to a higher genus hyperellipticover the subfield of the original field. This algorithm is the most efcient algorithm toattack ECDLP over a finite field of characteristic2. They gave a sufcient condition intheir paper that can help to find an elliptic curves, if it can use the GHS algorithm attacks.And they claimed that there only a few of the elliptic curves did not satisfy the condition.In my paper, I get a a necessary and sufcient condition that can determine thefeasibility of using GHS algorithm. This condition is easy to calculate. Then we give aninequality which we can use it to estimate the number of the elliptic curves that satisfiedthe condition. And the inequality can give an upper bound of the number of dangerouselliptic curves. At last, we analysis the computational complexity with diferent ellipticcurves,it verified that our work extends the scope of GHS algorithm.