Paper 2013/487

Classification of Elliptic/hyperelliptic Curves with Weak Coverings against the GHS attack under an Isogeny Condition

Tsutomu Iijima, Fumiyuki Momose, and Jinhui Chao

Abstract

The GHS attack is known to map the discrete logarithm problem(DLP) in the Jacobian of a curve $C_0$ defined over the $d$ degree extension $k_d$ of a finite field $k$ to the DLP in the Jacobian of a new curve $C$ over $k$ which is a covering curve of $C_0$, then solve the DLP of curves $C/k$ by variations of index calculus algorithms. It is therefore important to know which curve $C_0/k_d$ is subjected to the GHS attack, especially those whose covering $C/k$ have the smallest genus $g(C)=dg(C_0)$, which we called satisfying the isogeny condition. Until now, 4 classes of such curves were found by Thériault and 6 classes by Diem. In this paper, we present a classification i.e. a complete list of all elliptic curves and hyperelliptic curves $$ of genus 2, 3 which possess $$ covering $$ of $$ under the isogeny condition (i.e. $$) in odd characteristic case. In particular, classification of the Galois representation of $$ acting on the covering group $$ is used together with analysis of ramification points of these coverings. Besides, a general existential condition of a model of $$ over $$ is also obtained. As the result, a complete list of all defining equations of curves $$ with covering $$ are provided explicitly. Besides the 10 classes of $$ already known, 17 classes are newly found.