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\"obner basis assumption with major consequences on several cryptanalysis problems, including binary ECDLP.
Category / Keywords: public-key cryptography / elliptic curve cryptosystem, discrete logarithm problem, index calculus, Semaev’s summation polynomials, multivariate polynomial systems, Gr\"obner basis Date: received 21 Apr 2015 Contact author: cs at isit or jp; christophe petit@ucl ac uk Available format(s): PDF | BibTeX Citation Version: 20150423:125125 (All versions of this report) Short URL: ia.cr/2015/358