In this paper we introduce the notion of the last fall degree of a polynomial system, which is independent of choice of a monomial order. We then develop complexity bounds on solving polynomial systems based on this last fall degree.
We prove that HFE systems have a small last fall degree, by showing that one can do division with remainder after Weil descent. This allows us to solve HFE systems unconditionally in polynomial time if the degree of the defining polynomial and the cardinality of the base field are fixed.
For the ECDLP over a finite field of characteristic 2, we provide computational evidence that raises doubt on the validity of the first fall degree assumption, which was widely adopted in earlier works and which promises sub-exponential algorithms for ECDLP. In addition, we construct a Weil descent system from a set of summation polynomials in which the first fall degree assumption is unlikely to hold. These examples suggest that greater care needs to be exercised when applying this heuristic assumption to arrive at complexity estimates.
These results taken together underscore the importance of rigorously bounding last fall degrees of Weil descent systems, which remains an interesting but challenging open problem.Category / Keywords: discrete logarithm problem, elliptic curve cryptosystem, complexity theory Original Publication (in the same form): IACR-CRYPTO-2015 Date: received 9 Jun 2015, last revised 9 Jun 2015 Contact author: kosters at gmail com Available format(s): PDF | BibTeX Citation Version: 20150617:155848 (All versions of this report) Short URL: ia.cr/2015/573 Discussion forum: Show discussion | Start new discussion