Unconditional complexity of Gröbner-basis solving of the generalized MinRank problem: the Fröberg-type maximal-rank conjecture in the over-determined regime and polynomiality of F5 in the degree of the ideal

The generalized MinRank problem — computing the locus where an n×m matrix of generic homogeneous polynomials of degree D in k variables has rank at most r — is a central computational problem of multivariate and rank-metric post-quantum cryptography. Faugère, Safey El Din and Spaenlehauer (J. Symbolic Comput. 55:30–58, 2013) analyzed its minors modeling (the determinantal ideal generated by the (r+1)-minors of the matrix), giving closed-form Hilbert series, degree of regularity, degree, and F5+FGLM arithmetic complexity bounds under genericity assumptions. Caminata and Gorla (2021) later made the under-defined and well-defined regimes (k at least (n−r)(m−r)) unconditional. Two open cores identified in the source remain open as of 2026. First, in the cryptographically central over-determined regime k < (n−r)(m−r), all closed-form statements are conditional on an unproven Fröberg-type maximal-rank conjecture (Conjecture 12 of the published paper) asserting that multiplication by a generic quasi-homogeneous form of weight degree D on the specialized determinantal ideal has maximal rank. Second, it is unknown whether the actual arithmetic complexity of the F5 algorithm on these determinantal systems is polynomial in the degree of the ideal for all parameter families: for the family n = m with r and D fixed, the proved upper bound grows faster than any fixed polynomial in the degree, and the source explicitly states that the true behavior is an open problem.

Background

The MinRank problem is a computational problem at the heart of multivariate public-key cryptography and rank-metric coding theory: given matrices $M_1,\dots,M_k$ over a field $\mathbb{K}$, find scalars $x_1,\dots,x_k$ such that the linear combination $\sum_i x_i M_i$ has rank at most $r$. Its generalized form asks for the set of points in $\mathbb{K}^k$ at which the evaluation of a given $n\times m$ matrix $M(x)$, whose entries are generic homogeneous polynomials of degree $D$ in $x_1,\dots,x_k$, has rank at most $r$. Solving MinRank underlies the cryptanalysis of HFE (Hidden Field Equations, a family of multivariate public-key schemes) and attacks on rank-metric code-based cryptography, and over-determined instances (fewer variables than the determinantal codimension) are exactly those arising in decoding and in recent MinRank-based post-quantum designs such as the Mirath signature scheme, whose security rests on uniformly random over-determined MinRank instances with a unique solution (as discussed by Bardet and Gilard, listed in the references).

A natural algebraic formulation is the minors modeling: the rank-at-most-$r$ locus is cut out by the determinantal ideal generated by all $(r+1)\times(r+1)$ minors of $M(x)$. In practice this ideal is solved by Gröbner bases (bases of polynomial ideals enabling exact solving, e.g. via normal forms): first a basis for the degree-reverse-lexicographic (grevlex) monomial ordering is computed with Faugère's $F_5$ algorithm — a signature-based matrix algorithm that builds elimination (Macaulay) matrices degree by degree while avoiding reductions to zero for generic homogeneous input — and then converted to a lexicographic basis with the FGLM algorithm at a cost cubic in the number of solutions. Two invariants control these costs. The degree of regularity $\mathrm{dreg}(I)$ is the smallest degree at which all monomials lie in the homogeneous ideal $I$; it bounds the degrees reached during the computation and hence the sizes of the Macaulay matrices. The degree of the ideal $\mathrm{DEG}(I)$ is its multiplicity — for a zero-dimensional ideal, the number of solutions counted with multiplicity — and measures the output size. Both are read off from the Hilbert series $\mathrm{HS}_I(t)$, the generating series of the dimensions of the graded pieces of the quotient ring. Genericity throughout means that a property holds on a non-empty Zariski-open subset of the coefficient space (Zariski topology: opens are complements of polynomial zero-loci).

Determinantal ideals of matrices of indeterminates are classically understood: the theory of determinantal rings establishes that they are Cohen–Macaulay (a homological regularity property of the quotient ring) of codimension $(n-r)(m-r)$ with known Hilbert series and explicit free resolutions. Faugère, Safey El Din and Spaenlehauer (FSS) studied what happens when each indeterminate $u_{i,j}$ of the symbolic matrix is replaced by a generic homogeneous polynomial of degree $D$ in $k$ variables — a quasi-homogeneous (weighted-degree) specialization in which each $u_{i,j}$ carries weight $D$ and each $x_i$ weight 1. Writing $A_r(t)$ for the $r\times r$ matrix with $(i,j)$-entry $\sum_{s\ge0}\binom{m-i}{s}\binom{n-j}{s}t^s$, and $[S(t)]_+$ for a power series truncated at its first non-positive coefficient, they proved that in the well-defined case $k=(n-r)(m-r)$ the Hilbert series of the specialized ideal $\mathcal{I}_r$ is $\det(A_r(t^D))(1-t^D)^{(n-r)(m-r)}/(t^{D\binom{r}{2}}(1-t)^k)$, giving $\mathrm{dreg}=Dr(m-r)+(D-1)k+1$, an explicit degree formula, and the arithmetic complexity bound $O(\binom{n}{r+1}\binom{m}{r+1}\binom{\mathrm{dreg}+k}{k}^{\omega}+k\,\mathrm{DEG}^{3})$, where $2\le\omega\le3$ is a feasible exponent of matrix multiplication.

The under-defined ($k>(n-r)(m-r)$) and well-defined ($k=(n-r)(m-r)$) regimes are now understood unconditionally: Caminata and Gorla, combining the classical minimal free resolutions of determinantal rings with the fact that the solving degree of the minors system is bounded by the Castelnuovo–Mumford regularity of the ideal (a homological complexity invariant), gave a concise unconditional proof that recovers and extends the FSS solving-degree bounds for $k\ge(m-r)(n-r)$, and made the genericity conditions explicit and checkable over any field.

What remains conditional is the over-determined regime $k<(n-r)(m-r)$. There, FSS derive the truncated Hilbert series $\mathrm{HS}_{\mathcal{I}_r}(t)=\left[(1-t^D)^{nm-(n+m-r)r}\frac{\det A_r(t^D)}{t^{D\binom{r}{2}}(1-t)^k}\right]_+$ and the induced degree-of-regularity, degree and complexity formulas only under a variant of Fröberg's conjecture — Fröberg's 1985 conjecture that an ideal generated by generic forms has the Hilbert series predicted by maximal-rank behavior of the multiplication maps, itself open in general. The FSS variant (Conjecture 12 in the published paper; Conjecture 1 in the arXiv version) concerns generic quasi-homogeneous forms on the determinantal ideal over a function field in auxiliary indeterminates, stated precisely in the problem statement below.

Problem Statement

Resolve the open complexity questions that Faugère, Safey El Din and Spaenlehauer left open for Gröbner-basis solving of the generalized MinRank problem (minors modeling). The common objective is an unconditional and sharp arithmetic-complexity characterization of solving generic generalized MinRank instances in every parameter regime, through the two linked open questions below.

(1) Maximal-rank conjecture (over-determined regime, k < (n−r)(m−r)). Prove or disprove the Fröberg-type conjecture stated as Conjecture 12 in the published paper (Conjecture 1 in its arXiv version). Let $\mathbb{K}(\mathfrak b,\mathfrak c)$ be the function field in auxiliary indeterminates $\mathfrak b, \mathfrak c$; let $U=(u_{i,j})$ be an $n\times m$ matrix of variables of weight $D$ and $X=(x_1,\dots,x_k)$ variables of weight 1 in the quasi-homogeneous (weighted) grading; let $\mathscr{D}_r$ be the ideal generated by the $(r+1)\times(r+1)$ minors of $U$; and for $\ell\ge1$ let $g_{\ell+1}$ be a generic quasi-homogeneous form of weight degree $D$, i.e. a linear form in the $u_{i,j}$ with coefficients $\mathfrak c$ plus a homogeneous degree-$D$ form in the $x_i$ with coefficients $\mathfrak b$. The conjecture asserts that for every $\ell$ and every weight degree $i$, the multiplication map $\mathbb{K}(\mathfrak b,\mathfrak c)[U,X]_i/\left(\mathscr{D}_r+\langle g_1,\dots,g_\ell\rangle\right)_i \xrightarrow{\times g_{\ell+1}} \mathbb{K}(\mathfrak b,\mathfrak c)[U,X]_{i+D}/\left(\mathscr{D}_r+\langle g_1,\dots,g_\ell\rangle\right)_{i+D}$ has maximal rank, i.e. is injective or surjective. A proof makes the truncated Hilbert-series formula $\mathrm{HS}_{\mathcal{I}_r}(t)=[(1-t^D)^{nm-(n+m-r)r}\det A_r(t^D)/(t^{D\binom{r}{2}}(1-t)^k)]_+$ and the induced degree-of-regularity, degree and F5+FGLM complexity bounds for the over-determined regime unconditional; a disproof must exhibit parameters for which the map fails maximal rank generically.

(2) Polynomiality of F5 in the degree of the ideal. Determine whether the actual arithmetic complexity of the $F_5$ algorithm (matrix-F5, counting arithmetic operations in the base field, on the minors system of a generic instance) is polynomial in the degree of the ideal for all families of parameters of the generalized MinRank problem, or whether there exist families — for instance $n=m\to\infty$ with $r$ and $D$ fixed, where the currently proved upper bound grows faster than any fixed polynomial in $\mathrm{DEG}(\mathcal{I}_r)$ — for which it is not. The question concerns the true cost of the algorithm, not the sharpness of the current bound.

References

1. Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer. On the complexity of the generalized MinRank problem. Journal of Symbolic Computation 55:30–58, 2013. DOI: 10.1016/j.jsc.2013.03.004, https://doi.org/10.1016/j.jsc.2013.03.004 (arXiv:1112.4411, https://arxiv.org/abs/1112.4411)
2. Alessio Caminata, Elisa Gorla. The complexity of MinRank. In: Women in Numbers Europe III, Association for Women in Mathematics Series, Springer, pp. 163–169, 2021. DOI: 10.1007/978-3-030-77700-5_5, https://doi.org/10.1007/978-3-030-77700-5_5 (arXiv:1905.02682, https://arxiv.org/abs/1905.02682)
3. Alessio Caminata, Elisa Gorla. Solving Multivariate Polynomial Systems and an Invariant from Commutative Algebra. In: Arithmetic of Finite Fields (WAIFI 2020), Lecture Notes in Computer Science 12542, pp. 3–36, Springer, 2021. DOI: 10.1007/978-3-030-68869-1_1, https://doi.org/10.1007/978-3-030-68869-1_1
4. Magali Bardet, Alban Gilard. Computation of the Hilbert Series for the Support-Minors Modeling of the MinRank Problem. arXiv:2502.12721, 2025. https://arxiv.org/abs/2502.12721
5. Daniel Cabarcas, Giulia Gaggero, Elisa Gorla. The complexity of the SupportMinors Modeling for the MinRank Problem. Designs, Codes and Cryptography 94(4), 2026. DOI: 10.1007/s10623-025-01800-y, https://doi.org/10.1007/s10623-025-01800-y (arXiv:2506.06547, https://arxiv.org/abs/2506.06547)
6. Mats Boij, Eric Dannetun, Samuel Lundqvist. Independence of generic forms and the Fröberg conjecture. arXiv:2605.03872, 2026. https://arxiv.org/abs/2605.03872
7. Qihang Wang, Dongming Zhang. Fröberg's Conjecture for Quintics and Septics in Four Variables. arXiv:2608.24797, 2026. https://arxiv.org/abs/2608.24797
8. Ralf Fröberg. An inequality for Hilbert series of graded algebras. Mathematica Scandinavica 56:117–144, 1985. DOI: 10.7146/math.scand.a-12092, https://doi.org/10.7146/math.scand.a-12092
9. Sriram Gopalakrishnan, Vincent Neiger, Mohab Safey El Din. Optimized Gröbner basis algorithms for maximal determinantal ideals and critical point computations. Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation (ISSAC 2024), ACM, pp. 400–409, 2024. DOI: 10.1145/3666000.3669713, https://doi.org/10.1145/3666000.3669713 (arXiv:2402.07353, https://arxiv.org/abs/2402.07353)
10. Sriram Gopalakrishnan. On the arithmetic complexity of computing Gröbner bases of comaximal determinantal ideals. arXiv:2403.02160, 2024. https://arxiv.org/abs/2403.02160
11. Magali Bardet, Jean-Charles Faugère, Bruno Salvy. On the complexity of the F5 Gröbner basis algorithm. Journal of Symbolic Computation 70:49–70, 2015. DOI: 10.1016/j.jsc.2014.09.025, https://doi.org/10.1016/j.jsc.2014.09.025 (arXiv:1312.1655, https://arxiv.org/abs/1312.1655)
12. Jérémy Berthomieu, Alin Bostan, Andrew Ferguson, Mohab Safey El Din. Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems. Journal of Algebra 602:154–180, 2022. DOI: 10.1016/j.jalgebra.2022.03.002, https://doi.org/10.1016/j.jalgebra.2022.03.002 (arXiv:2203.10021, https://arxiv.org/abs/2203.10021)