A Weil Descent Attack against Elliptic Curve Cryptosystems over Quartic Extension Fields

Seigo ARITA; Kazuto MATSUO; Koh-ichi NAGAO; Mahoro SHIMURA

doi:10.1093/ietfec/e89-a.5.1246

A Weil Descent Attack against Elliptic Curve Cryptosystems over Quartic Extension Fields

Seigo ARITA, Kazuto MATSUO, Koh-ichi NAGAO, Mahoro SHIMURA

Full Text Views

0

Share
Cite this

Summary :

This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a DLP on a special form, called Scholten form, over the same field. Second, one reduces the DLP on the Scholten form to a DLP on a genus two hyperelliptic curve over the quadratic extension of k. Then, one reduces the DLP on the hyperelliptic curve to one on a C_ab model over k. Finally, one obtains the discrete-log of original DLP by applying the Gaudry method to the DLP on the C_ab model. In order to carry out the scenario, this paper shows that many of elliptic curve discrete-log problems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve discrete-log problems over quadratic extension fields, and that almost all of the genus two hyperelliptic curve discrete-log problems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked uniformly.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1246-1254

Publication Date: 2006/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.5.1246

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Seigo ARITA, Kazuto MATSUO, Koh-ichi NAGAO, Mahoro SHIMURA, "A Weil Descent Attack against Elliptic Curve Cryptosystems over Quartic Extension Fields" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 5, pp. 1246-1254, May 2006, doi: 10.1093/ietfec/e89-a.5.1246.
Abstract: This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a DLP on a special form, called Scholten form, over the same field. Second, one reduces the DLP on the Scholten form to a DLP on a genus two hyperelliptic curve over the quadratic extension of k. Then, one reduces the DLP on the hyperelliptic curve to one on a C_ab model over k. Finally, one obtains the discrete-log of original DLP by applying the Gaudry method to the DLP on the C_ab model. In order to carry out the scenario, this paper shows that many of elliptic curve discrete-log problems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve discrete-log problems over quadratic extension fields, and that almost all of the genus two hyperelliptic curve discrete-log problems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked uniformly.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1246/_p

Copy

@ARTICLE{e89-a_5_1246,
author={Seigo ARITA, Kazuto MATSUO, Koh-ichi NAGAO, Mahoro SHIMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Weil Descent Attack against Elliptic Curve Cryptosystems over Quartic Extension Fields},
year={2006},
volume={E89-A},
number={5},
pages={1246-1254},
abstract={This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a DLP on a special form, called Scholten form, over the same field. Second, one reduces the DLP on the Scholten form to a DLP on a genus two hyperelliptic curve over the quadratic extension of k. Then, one reduces the DLP on the hyperelliptic curve to one on a C_ab model over k. Finally, one obtains the discrete-log of original DLP by applying the Gaudry method to the DLP on the C_ab model. In order to carry out the scenario, this paper shows that many of elliptic curve discrete-log problems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve discrete-log problems over quadratic extension fields, and that almost all of the genus two hyperelliptic curve discrete-log problems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked uniformly.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1246},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - A Weil Descent Attack against Elliptic Curve Cryptosystems over Quartic Extension Fields
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1246
EP - 1254
AU - Seigo ARITA
AU - Kazuto MATSUO
AU - Koh-ichi NAGAO
AU - Mahoro SHIMURA
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1246
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a DLP on a special form, called Scholten form, over the same field. Second, one reduces the DLP on the Scholten form to a DLP on a genus two hyperelliptic curve over the quadratic extension of k. Then, one reduces the DLP on the hyperelliptic curve to one on a C_ab model over k. Finally, one obtains the discrete-log of original DLP by applying the Gaudry method to the DLP on the C_ab model. In order to carry out the scenario, this paper shows that many of elliptic curve discrete-log problems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve discrete-log problems over quadratic extension fields, and that almost all of the genus two hyperelliptic curve discrete-log problems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked uniformly.
ER -