Cryptology ePrint Archive: Report 2015/805

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

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

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

Date: received 11 Aug 2015, last revised 18 Sep 2015

Contact author: tiijima at jt3 so-net ne jp

Available format(s): PDF | BibTeX Citation

Version: 20150918:132050 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]