💻 computer science

The complexity of solving a system of equations of the same degree

This paper establishes upper bounds on the degree of regularity and solving complexity for systems of equations with uniform degree, which are prevalent in cryptography, by analyzing their dependence on the number of variables, equations, and equation degree.

Original authors: Giulia Gaggero, Elisa Gorla

Published 2026-02-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Giulia Gaggero, Elisa Gorla

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to crack a complex lock. In the world of cryptography, this lock is often a giant, tangled mess of mathematical equations. To open it, you need to find the specific numbers (variables) that make all the equations true at the same time.

This paper is about figuring out how hard it is to crack these locks and providing a guaranteed "worst-case" estimate of the effort required, without relying on lucky guesses.

Here is a breakdown of the paper's ideas using everyday analogies:

1. The Problem: The Tangled Knot

Cryptography often relies on the idea that solving a system of polynomial equations (like $x^2 + y = 5$ and $xy + z = 10$) is incredibly difficult. If you can't solve them quickly, the secret key remains safe.

To crack these systems, mathematicians use a powerful tool called a Gröbner basis. Think of this tool as a giant, automated sorting machine. It takes your messy equations and rearranges them into a neat, solvable list. However, this machine has to go through many "rounds" of sorting. The more rounds it needs, the more time and computer power it takes.

The paper focuses on a specific metric called the degree of regularity. You can think of this as the "height" of the sorting machine's ladder.

Low height: The machine sorts the equations quickly. The lock is weak.
High height: The machine has to climb very high to find the solution. The lock is strong.

2. The Old Way: Guessing the Height

Previously, experts tried to estimate this "height" by assuming the equations were random and perfectly balanced (a concept called "semiregular"). It's like assuming every knot you encounter is a standard, predictable tangle.

The flaw: This is just a guess. Sometimes, the knot is actually a weird, tricky shape that doesn't follow the rules. If you guess wrong, you might think a lock is safe when it's actually easy to break, or vice versa.

3. The New Way: A Guaranteed Ceiling

The authors of this paper say, "Let's stop guessing. Let's prove a hard limit."

They focus on systems where all the equations have the same degree (e.g., they are all quadratic, or all cubic). They prove that no matter how the equations are arranged, there is a mathematical ceiling (an upper bound) on how high the sorting ladder needs to go.

The Analogy of the Library:
Imagine you have a library with $n$ shelves and $m$ books.

The degree of the equations is how thick the books are.
The number of variables is the number of shelves.
The number of equations is the number of books.

The authors prove that if you have a certain number of books of the same thickness, you can mathematically guarantee that you will never need to climb higher than a specific shelf to find the right order. They calculate this maximum shelf number based strictly on:

How many books you have ( $m$ ).
How many shelves there are ( $n$ ).
How thick the books are (the degree).

4. The "Field Equations" Twist

In cryptography, there's a special rule: numbers usually wrap around (like a clock). If you are working with numbers 0 to 9, then $10$ becomes $0$. In math, this is adding "field equations."

The paper also looks at what happens when you add these "wrap-around" rules to the mix.

Without wrap-around: The sorting machine might need to climb a certain height.
With wrap-around: The machine might find the solution faster because the rules are stricter.

The authors provide a new, guaranteed ceiling for this scenario too. They show that even with these extra rules, there is a limit to how hard the problem can get, and they calculate exactly what that limit is.

5. Why This Matters (The "Proven" Advantage)

The paper admits that their calculated "ceiling" might be a bit higher than the actual height needed for a specific, lucky set of equations.

The Heuristic (Old Way): "I bet this knot is easy to untie because it looks random." (Fast, but risky).
The Proof (This Paper): "I cannot prove this knot is easy, but I can prove it will never take more than 100 steps to untie." (Slower estimate, but 100% safe).

This is crucial for security. If a cryptographer wants to design a lock that is safe for the next 50 years, they need to know the worst-case scenario. They don't want to rely on the hope that the equations will be "nice." They want a mathematical guarantee that the "sorting machine" will never have to climb higher than a safe height.

Summary

This paper provides a mathematical safety net. It tells us: "If you have a system of equations with these specific numbers of variables and equations, you can be 100% certain that solving it will not require more computational effort than X."

It replaces the guesswork of "it probably looks random, so it's hard" with the certainty of "we have proven it cannot be harder than this." This allows cryptographers to design systems with a known, guaranteed level of security against current mathematical attacks.

Technical Summary: Complexity of Solving Systems of Equations of the Same Degree

Problem Statement

The security of numerous cryptographic schemes, particularly in multivariate cryptography and post-quantum settings, relies on the computational hardness of solving systems of multivariate polynomial equations over finite fields. The complexity of solving such systems via Gröbner basis methods is primarily governed by the degree of regularity ( $d_{reg}$ ) and the solving degree. While the degree of regularity provides an upper bound on the complexity of Gröbner basis computations, it is often difficult to compute or estimate for systems of cryptographic size.

Common practice relies on the heuristic assumption that systems are semiregular (or cryptographic semiregular), which yields explicit formulas for the degree of regularity. However, this assumption is not always valid; there exist parameter choices and fields where no semiregular sequence exists. Consequently, there is a need for proven, non-heuristic upper bounds on the degree of regularity and solving degree that apply to systems where the degree of regularity is finite, without relying on the semiregularity assumption.

Methodology

The authors approach the problem using tools from commutative algebra, specifically focusing on systems where the ideal generated by the top-degree parts of the polynomials contains a regular sequence of $n$ polynomials in a given degree $D$ .

Framework: The paper considers a system $F = \{f_1, \dots, f_m\}$ of $m$ polynomials in $n$ variables over a field $F$ . The analysis assumes the top-degree parts $f_1^{top}, \dots, f_m^{top}$ are linearly independent and that the system is regular in degree $D$ (meaning the ideal generated by the top-degree parts contains a regular sequence of $n$ polynomials of degree $D$ ).
Reduction to LPP Ideals: To bound the Castelnuovo-Mumford regularity (which equals the degree of regularity when finite), the authors utilize the Eisenbud-Green-Harris (EGH) Conjecture. This conjecture posits that among all homogeneous ideals containing a regular sequence of specific degrees, the Lex-Plus-Powers (LPP) ideal has the maximal regularity.
Combinatorial Analysis: The authors construct specific LPP ideals associated with the given parameters ( $n, m, D$ ). By analyzing the structure of these ideals under the lexicographic order, they determine the regularity of the LPP ideal, which serves as an upper bound for the regularity of the original system (conditional on the EGH Conjecture).
Field Equations: The methodology is extended to systems augmented with field equations ( $x_i^q - x_i$ ), which is critical for systems over finite fields $\mathbb{F}_q$ , particularly when the degree of the equations $D$ is greater than or equal to the field size $q$ .

Key Contributions and Results

1. Upper Bounds for Systems Regular in Degree $D$ (Without Field Equations)

Theorem 23 provides a sharp upper bound for the degree of regularity of a system of $m$ equations of degree $D$ in $n$ variables, assuming the system is regular in degree $D$ .

The bound depends on the number of equations ( $m$ ), variables ( $n$ ), and degree ( $D$ ).
The formula involves identifying unique integers $k$ and $t$ such that $m-n$ falls within a specific interval defined by combinatorial sums ( $\sigma_{k,t}$ ).
The resulting bound is: $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$ .
This bound is sharp for all values of $m, n, D$ and is met by systems where the top-degree parts form a specific LPP ideal.

Corollary 27 translates this into an upper bound on the solving degree for mutant algorithms:
$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$

2. Upper Bounds for Systems with Field Equations

The paper addresses the case where field equations are added to the system, which is essential when $D \ge q$ .

Proposition 31: For very overdetermined systems (where $m$ exceeds the dimension of the space of polynomials modulo field equations), the degree of regularity is exactly $D$ .
Theorem 33: For systems where $q \le D \le n(q-1)$ $q \leq D \leq n (q - 1)$ and the top-degree parts are linearly independent modulo the field equations, the authors provide an upper bound on the degree of regularity.
- The bound is derived by analyzing the position of the $m$ -th monomial in the lexicographic ordering of degree $D$ monomials modulo $(x_1^q, \dots, x_n^q)$ .
- The bound is expressed in terms of $B = q - t + (n - k)(q - 1)$ , where $k$ and $t$ are determined by the interval containing $m$ .
- Depending on specific conditions regarding $m, D,$ and $t$ , the bound is either $B$ or $B-1$ .

Corollary 34 specializes these results for binary systems ( $q=2$ ), providing simplified formulas for the degree of regularity and solving degree for systems of degree $D$ over $\mathbb{F}_2$ .

3. Application to Specific Schemes

The authors apply their bounds to concrete cryptographic schemes:

Cubic Simple Matrix: They derive a proven bound $d_{reg} \le 2n - 1$ , which is the first proven bound for this system, contrasting with previous heuristic estimates.
Unbalanced Oil and Vinegar (UOV): The bounds are applied to UOV systems over $\mathbb{F}_2$ , demonstrating how the degree of regularity behaves when field equations are included.

Significance and Claims

The paper claims significance primarily in providing proven, non-heuristic bounds for the complexity of solving polynomial systems.

Reliability: Unlike estimates based on the semiregularity assumption (which may fail for certain parameters), these bounds hold for any system where the degree of regularity is finite and the system is regular in a given degree.
Generality: The results apply to systems over arbitrary fields and cover both cases with and without field equations.
Sharpness: The bounds are described as "sharp," meaning they are achieved by specific systems (LPP ideals), offering a realistic worst-case estimate for security analysis.
Limitations: The authors explicitly acknowledge that their bounds are generally less tight (i.e., higher) than those obtained under the semiregularity heuristic. However, they argue that this trade-off is necessary to avoid unproven assumptions, particularly in scenarios where semiregular sequences do not exist.

The work does not propose new algorithms or experimental implementations but rather establishes theoretical limits on the complexity of existing Gröbner basis methods (both standard and mutant) for a broad class of polynomial systems relevant to cryptography.