Paper 2015/984

Complexity of ECDLP under the First Fall Degree Assumption

Koh-ichi Nagao

Abstract

Semaev shows that under the first fall degree assumption, the complexity of ECDLP over $\bF_{2^n}$, where $n$ is the input size, is $O(2^{n^{1/2+o(1)}})$. In his manuscript, the cost for solving equations system is $O((nm)^{4w})$, where $m$ ($2 \le m \le n$) is the number of decomposition and $w \sim 2.7$ is the linear algebra constant. It is remarkable that the cost for solving equations system under the first fall degree assumption, is poly in input size $n$. He uses normal factor base and the revalance of "Probability that the decomposition success" and "size of factor base" is done. %So that the result is induced. Here, using disjoint factor base to his method, "Probability that the decomposition success becomes $ \sim 1$ and taking the very small size factor base is useful for complexity point of view. Thus we have the result that states \\ "Under the first fall degree assumption, the cost of ECDLP over $\bF_{2^n}$, where $n$ is the input size, is $O(n^{8w+1})$." Moreover, using the authors results, in the case of the field characteristic $\ge 3$, the first fall degree of desired equation system is estimated by $\le 3p+1$. (In $p=2$ case, Semaev shows it is $\le 4$. But it is exceptional.) So we have similar result that states \\ "Under the first fall degree assumption, the cost of ECDLP over $\bF_{p^n}$, where $n$ is the input size and (small) $p$ is a constant, is $O(n^{(6p+2)w+1})$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
ECDLPFirst fall degree assumptionpolynomial time algorithm
Contact author(s)
nagao @ kanto-gakuin ac jp
History
2015-10-12: received
Short URL
https://ia.cr/2015/984
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/984,
      author = {Koh-ichi Nagao},
      title = {Complexity of ECDLP under the First Fall Degree Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/984},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/984}},
      url = {https://eprint.iacr.org/2015/984}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.