Welcome to the resource topic for 2013/549
Title:
Equations System coming from Weil descent and subexponential attack for algebraic curve cryptosystem
Authors: 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öbner 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.
ePrint: https://eprint.iacr.org/2013/549
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .