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

*Tsutomu Iijima and 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 $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.

**Category / Keywords: **public-key cryptography / Weil descent attack, GHS attack, Elliptic curve cryptosystems, Hyperelliptic curve cryptosystems, Index calculus, Galois representation

**Date: **received 10 Aug 2013, last revised 18 Feb 2015

**Contact author: **tiijima at jt3 so-net ne jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20150218:104852 (All versions of this report)

**Short URL: **ia.cr/2013/487

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]