Paper 2013/487 Original: eprint.iacr.org/2013/487 ↗

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

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 $C_{0}/k_{d}$ of genus 2, 3 which possess $(2,...,2)$ covering $C/k$ of $\Bbb{P}^1$ under the isogeny condition (i.e. $g(C)=d \cdot g(C_{0})$) in odd characteristic case. In particular, classification of the Galois representation of $\Gal(k_{d}/k)$ acting on the covering group $\cov(C/\Bbb{P}^1)$ is used together with analysis of ramification points of these coverings. Besides, a general existential condition of a model of $C$ over $k$ is also obtained. As the result, a complete list of all defining equations of curves $C_0/k_d$ with covering $C/k$ are provided explicitly. Besides the 10 classes of $C_0/k_d$ already known, 17 classes are newly found.