**Equations System coming from Weil descent and subexponential attack for algebraic curve cryptosystem**

*Koh-ichi Nagao*

**Abstract: **Faugére et al. shows that the decomposition problem of a point of
elliptic curve over binary field $F_{2^n}$ reduces to solving low degree equations system
over $F_2$ coming from Weil descent. Using this method, the discrete logarithm problem of elliptic curve over
$F_{2^n}$ reduces to linear constrains, i.e., solving equations system using linear algebra
of monomial modulo field equations, and its complexity is expected to be subexponential of input size $n$. However, it is pity that at least using linear constrains, it is exponential.
Petit et al. shows that assuming first fall degree assumption,
from which the complexity of solving low degree equations system using Gr\"obner basis computation is subexponential, its total complexity is heuristically subexponential.
On the other hands, the author shows that the decomposition problem of Jacobian of plane curve over $F_{p^n}$ also essentially reduces to solving low degree equations system over $F_p$ coming from Weil descent. In this paper, we revise (precise estimation of first fall degree) the results of Petit et al. and show that the discrete logarithm problem of elliptic curve over small characteristic field $F_{p^n}$ is subexponential of input size $n$, and the discrete logarithm problem of Jacobian of small genus curve over small characteristic field $F_{p^n}$ is also subexponential of input size $n$, under first fall degree assumption.

**Category / Keywords: **Decomposition Attack, ECDLP, first fall degree

**Date: **received 31 Aug 2013, last revised 5 Nov 2013

**Contact author: **nagao at kanto-gakuin ac jp

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

**Note: **Revise 6 NOV.
In \S 3, we estimate the degree of the $[\vec{m_0} \vec{F}]^{\downarrow}_k$ for some
monomial $\vec{m_0}:=\prod_{i=1}^d \vec{X_i}^{p^{\alpha}-1-E_i} \in \bF_{p^n}[\vec{X_1},...,\vec{X_d}]$.
For our aim, the solution of the equations system
$\{ [\vec{F}]_i^{\downarrow}=0 \, | 1\le i\le n \} \cup \{f=0 \, | f \in S_{fe} \}$
must equals to
$\{ [\vec{m_0} \vec{F}]_i^{\downarrow}=0 \, | 1\le i\le n \} \cup \{f=0 \, | f \in S_{fe} \}$.
However, it is not true. Let $\tau \in \bF_{p^n} \setminus \{\sum_{i=1}^{n'} x_i w_i \, | \, x_i \in \bF_p \}$,
and take new
$\vec{m_0}$ by $\prod_{i=1}^d (\vec{X_i}-\tau)^{p^{\alpha}-1-E_i} \in \bF_{p^n}[\vec{X_1},...,\vec{X_d}]$
(not monomial but polynomial), we have this property and all lemmas still hold. }

**Version: **20131105:172901 (All versions of this report)

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

[ Cryptology ePrint archive ]