On the last fall degree of zero-dimensional Weil descent systems (Q1690789)

Let \(R=K[x_1,\dots,x_n]\) be a polynomial ring over a field \(K\). Let \(R_{\leq i}\) denote the set of all polynomials in \(R\) of degree at most \(i\). In addition, we assume that \(F=\{f_1,\dots,f_k\}\subset R\) is a generating set of a zero-dimensional ideal. For each \(i\), we let \(V_{F,i}\) be the smallest \(K\)-vector space of \(R_{\leq i}\) such that the following conditions hold: {\parindent=0.7cm\begin{itemize}\item[1.] \(\{f\in F \mid \deg(f)\leq i\}\subset V_{F,i}\), \item[2.] if \(g\in V_{F,i}\) and if \(h\in R\) with \(\deg(hg)\leq i\) then \(hg\in V_{F,i}\). \end{itemize}} The first fall degree of \(F\) is defined to be the first \(d\) such that \(V_{F,d} \cap R_{d-1}\neq V_{F,d}\). Indeed, it is the smallest integer \(d\) such that for any \(f\) in the ideal generated by \(F\), we have \(f\in V_{\max\{\deg(f),d\}}\). This integer is denoted by \(d_F\). In the first part of the paper, the authors present new complexity bounds for solving a zero-dimensional system depending on the new parameter \(d_F\). In the second part, they deal with finite fields. Let \(K\) be a finite field of cardinality \(q^m\) and \(K'\subset K\) the sub-field of cardinality \(q\). Assume that \(F\subset K[x_1,\dots ,x_n]\) generates a zero-dimensional ideal. Then, they give an upper bound of the last fall degree of the Weil descent system of \(F\) from \(K\) to \(K'\), depending on \(q,n\) and \(d_F\). As a consequence, one can apply these results to show a weakness in the cryptographic protocols HFE and multi-HFE.