Paper 2015/805

A classification of elliptic curves with respect to the GHS attack in odd characteristic

Tsutomu Iijima, Fumiyuki Momose, and Jinhui Chao

Abstract

The GHS attack is known to solve discrete logarithm problems (DLP) in the Jacobian of a curve C_0 defined over the d degree extension field k_d of k:=GF(q) by mapping it to the DLP in the Jacobian of a covering curve C of C_0 over k. Recently, classifications for all elliptic curves and hyperelliptic curves C_0/k_d of genus 2,3 which possess (2,...,2)-covering C/k of P^1 were shown under an isogeny condition (i.e. when g(C) = d * g(C_0)). This paper presents a systematic classification procedure for hyperelliptic curves in the odd characteristic case. In particular, we show a complete classification of elliptic curves C_0 over k_d which have (2,...,2)-covering C/k of P^1 for d=2,3,5,7. It has been reported by Diem that the GHS attack fails for elliptic curves C_0 over odd characteristic definition field k_d with prime extension degree d greater than or equal to 11 since g(C) become very large. Therefore, for elliptic curves over k_d with prime extension degree d, it is sufficient to analyze cases of d=2,3,5,7. As a result, a complete list of all elliptic curves C_0/k which possess (2,...,2)-covering C/k of P^1 thus are subjected to the GHS attack with odd characteristic and prime extension degree d is obtained.