Paper 2015/358

On Generalized First Fall Degree Assumptions

Yun-Ju Huang, Christophe Petit, Naoyuki Shinohara, and Tsuyoshi Takagi

Abstract

The first fall degree assumption provides a complexity approximation of Gröbner basis algorithms when the degree of regularity of a polynomial system cannot be precisely evaluated. Most importantly, this assumption was recently used by Petit and Quisquater's to conjecture that the elliptic curve discrete logarithm problem can be solved in subexponential time for binary fields (binary ECDLP). The validity of the assumption may however depend on the systems in play. In this paper, we theoretically and experimentally study the first fall degree assumption for a class of polynomial systems including those considered in Petit and Quisquater's analysis. In some cases, we show that the first fall degree assumption seems to hold and we deduce complexity improvements on previous binary ECDLP algorithms. On the other hand, we also show that the assumption is unlikely to hold in other cases where it would have very unexpected consequences. Our results shed light on a Gröbner basis assumption with major consequences on several cryptanalysis problems, including binary ECDLP.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
elliptic curve cryptosystemdiscrete logarithm problemindex calculusSemaev’s summation polynomialsmultivariate polynomial systemsGröbner basis
Contact author(s)
cs @ isit or jp
christophe petit @ ucl ac uk
History
2015-04-23: received
Short URL
https://ia.cr/2015/358
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/358,
      author = {Yun-Ju Huang and Christophe Petit and Naoyuki Shinohara and Tsuyoshi Takagi},
      title = {On Generalized First Fall Degree Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/358},
      year = {2015},
      url = {https://eprint.iacr.org/2015/358}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.