International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 04 September 2013

Koh-ichi Nagao
ePrint Report ePrint Report
Faug\\\'ere et al. shows that the decomposition problem of an element of elliptic curve over binary field $F_{2^n}$ reduces to solving low degree equations system over $bF_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 and using Gr\\\"obner basis computation, its 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 generalize ($p>2$ cases, Jacobian cases) and 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.

Expand

Additional news items may be found on the IACR news page.