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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Elliptic curve cryptosystemsHyperelliptic curve cryptosystemsIndex calculusGHS attackGalois representation
Contact author(s)
tiijima @ jt3 so-net ne jp
History
2015-09-18: last of 3 revisions
2015-08-13: received
See all versions
Short URL
https://ia.cr/2015/805
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/805,
      author = {Tsutomu Iijima and Fumiyuki Momose and Jinhui Chao},
      title = {A classification of elliptic curves with respect to the GHS attack in odd characteristic},
      howpublished = {Cryptology ePrint Archive, Paper 2015/805},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/805}},
      url = {https://eprint.iacr.org/2015/805}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.