Analysis of the GHS Weil descent attack on the ECDLP over characteristic two finite fields of composite degree

Abstract: In this paper, the authors analyze the Gaudry–Hess–Smart (GHS) Weil descent attack on the elliptic curve discrete logarithm problem (ECDLP) for elliptic curves defined over characteristic two finite fields of composite extension degree. For each such field F_2^N, where N is in [100,600], elliptic curve parameters are identified such that: (i) there should exist a cryptographically interesting elliptic curve E over F_2^N with these parameters; and (ii) the GHS attack is more efficient for solving the ECDLP in E(F_2^N) than for solving the ECDLP on any other cryptographically interesting elliptic curve over F_2^N. The feasibility of the GHS attack on the specific elliptic curves is examined over F_2¹⁷⁶, F_2²⁰⁸, F_2²⁷², F_2³⁰⁴ and F_2³⁶⁸, which are provided as examples in the ANSI X9.62 standard for the elliptic curve signature scheme ECDSA. Finally, several concrete instances are provided of the ECDLP over F_2^N, N composite, of increasing difficulty; these resist all previously known attacks, but are within reach of the GHS attack.