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

arXiv:2309.03855 · cs.CR, math.AG, math.CO · Submitted 2026-08-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "The complexity of solving a system of equations of the same degree".

Jane: The paper was written by Giulia Gaggero and Elisa Gorla from armasuisse.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: Welcome back to the show, everyone. Today we’re looking at a paper that just hit arXiv, and it’s called “The complexity of solving a system of equations of the same degree.” I’m here with Jane, and honestly, this one gets right into the weeds of cryptography.

Jane: It really does, Tom. And I think the title is actually a great entry point. When you see “equations of the same degree,” you might think of something like x squared plus y squared equals something, and then another equation that’s also quadratic. That’s exactly what a lot of real cryptographic systems look like.

Tom: Right, so the paper is from Giulia Gaggero and Elisa Gorla, and they’re tackling a question that’s been nagging at cryptographers for a while. If you have a bunch of equations that are all, say, cubic, and you want to solve them, how hard is that? And the answer isn’t just “hard,” it’s “we can prove it’s at most this hard.”

Jane: And that’s the key thing here. They’re not giving a heuristic guess. They’re giving upper bounds that are proven, assuming a famous conjecture in commutative algebra holds. So the complexity of solving these systems is bounded, and that bound depends on how many equations you have, how many variables, and the degree of those equations.

Tom: Exactly. And why does that matter? Because in multivariate cryptography, the whole security of a scheme rests on the assumption that solving these systems is infeasible. If you can prove a bound on how hard it is, you can actually say something concrete about the security you’re getting.

Jane: And that’s a big deal, because a lot of the time, people just assume a system behaves like a “random” one and then use that to estimate security. But that’s an assumption, not a proof. This paper gives you a proven ceiling, even if it’s not always the tightest possible.

Tom: So Jane, if I’m a cryptographer designing a new scheme, what do I do with this? I mean, do I just plug in my numbers and get a security level?

Jane: Kind of. You take your number of equations, your number of variables, and the degree, and the paper gives you a formula for the degree of regularity. That’s the thing that tells you how hard the system is to solve. And then you can say, “Okay, my system is at least this hard to break.”

Tom: That’s the practical hook. And the paper also handles the case where you add the so-called “field equations,” which is what you do when you’re working over a finite field and you want to make sure you’re only looking at actual solutions, not some abstract algebraic ones.

Jane: Right. And that’s where things get a bit more technical, but the bottom line is they have bounds for both cases. And they even apply it to a real scheme called the Cubic Simple Matrix encryption scheme, where they get a bound of two n minus one for the degree of regularity.

Tom: That’s a concrete number for a real system. And that’s what makes this paper exciting, because it’s not just abstract theory. It’s theory that lands on actual cryptographic constructions.

Jane: And it gives you a sense of what security you can hope for. If you know the ceiling, you can design your parameters to stay below it.

Tom: So we’ve got the title, we’ve got the gist. But I want to get into the actual method, because there’s a clever trick in here involving something called lex-segment ideals. That’s coming up next.

Jane: It sounds scary, but I promise we’ll break it down. Stick around.

Paper summary: Tom: So we’re back, and we’re still on “The complexity of solving a system of equations of the same degree.” Jane, you promised to break down the method. Let’s go.

Jane: Okay, so the core idea is that they want to bound the degree of regularity, which is like the “breaking point” of a polynomial system. If you’re doing Gaussian elimination on a matrix, the degree of regularity is the degree at which you finally have enough information to solve the system.

Tom: And that’s what determines the complexity of the whole thing. So how do they bound it?

Jane: They use a tool from commutative algebra called the Eisenbud-Green-Harris conjecture. It’s a well-known conjecture that says, roughly, that among all ideals that contain a certain kind of regular sequence, the one that grows the slowest is a very specific, structured ideal called a lex-plus-powers ideal.

Tom: And why is that useful?

Jane: Because if you can reduce your problem to studying these very structured ideals, you can compute their regularity exactly. And then you know that your original system can’t be worse than that.

Tom: So they’re essentially saying, “The worst case is this neat, ordered ideal, and we can compute its degree of regularity.” And that gives them the bound.

Jane: Exactly. And the clever part is figuring out which of these structured ideals corresponds to your system. You have m equations in n variables, and the difference m minus n tells you how “overdetermined” your system is. That difference places you in a specific interval, and that interval tells you which lex-plus-powers ideal to look at.

Tom: So it’s like a lookup table. You compute m minus n, you find your interval, and you get your bound.

Jane: That’s the idea. And the bound they get is sharp, meaning there are systems that actually achieve it. So you can’t do better with this method.

Tom: And they also handle the case where you add the field equations, which is what you do when you’re working over a finite field like F2 or Fq. That’s a separate theorem, and it’s a bit more involved because now you have to account for the fact that the variables satisfy x to the q equals x.

Jane: Right. And in that case, the bound depends on q, the field size, and on the degree D of your equations. They have a formula that again uses these structured ideals, but now with the field equations built in.

Tom: And there’s a nice result for very overdetermined systems. If you have enough equations, the degree of regularity is just D, the degree of the equations themselves. So you can’t make it any smaller.

Jane: That’s Proposition thirty-three in the paper, and it’s a nice sanity check. If you have tons of equations, the system is easy to solve, and the bound reflects that.

Tom: So the method is: reduce to a structured ideal, compute its regularity, and that gives you a proven ceiling. And the ceiling is sharp. That’s a solid summary.

Jane: And it’s all conditional on the Eisenbud-Green-Harris conjecture, which is widely believed to be true. So the results are solid, but they’re not unconditional.

Tom: So we have the method. But what does this mean for actual cryptosystems? That’s where I want to go next, because the paper applies this to a real scheme.

Jane: And that’s the fun part. Let’s get into it.

Improvements and implications: Tom: So we’re back, and we’re still on “The complexity of solving a system of equations of the same degree.” Jane, we said the paper applies this to a real scheme. Which one?

Jane: It’s the Cubic Simple Matrix encryption scheme. That’s a system of two n cubic equations in n variables. And the paper shows that the degree of regularity is at most two n minus one.

Tom: And that’s a proven bound, not a heuristic. So if someone tells you that scheme is secure because it’s “probably” hard to solve, this paper says, “No, here’s a ceiling, and it’s two n minus one.”

Jane: Exactly. And that’s a big deal because a lot of the security arguments in multivariate cryptography are based on heuristics. People assume the system is “semiregular,” which is a fancy way of saying it behaves like a random system. But that assumption can fail.

Tom: And the paper points out that there are choices of parameters where no semiregular sequence even exists. So the heuristic just doesn’t apply. But the bound in this paper always applies, as long as the degree of regularity is finite.

Jane: Right. And that’s the improvement. Instead of assuming your system is semiregular, you just need to know that it contains a regular sequence in the right degree. That’s a much weaker assumption, and it’s often true.

Tom: So the practical impact is that cryptographers can now get a proven upper bound on the complexity of breaking their scheme, even when the usual heuristics don’t apply.

Jane: And that’s important for designing new schemes. If you know the ceiling, you can choose your parameters so that the ceiling is high enough. You can say, “I want the degree of regularity to be at least this big, so I’ll use this many equations and this many variables.”

Tom: But there’s a catch, right? The bounds are proven, but they’re not always tight. For a semiregular system, the degree of regularity is often lower than the bound in this paper.

Jane: That’s true. The paper acknowledges that. The bounds are worst-case, so they’re not as sharp as what you’d get from the semiregular assumption. But they’re proven, and that’s worth a lot.

Tom: And there’s another practical angle. The paper also gives bounds on the solving degree, which is what actually matters when you run an algorithm like F4 or XL. So you’re not just getting a theoretical invariant; you’re getting a bound on the actual computation.

Jane: Exactly. And they use results from Semaev and Tenti, and from Salizzoni, to translate the degree of regularity bound into a solving degree bound. So you get a proven complexity estimate for the actual attack.

Tom: So the improvement here is: proven bounds, applicable to real schemes, even when heuristics fail. That’s a solid contribution.

Jane: And it gives the community a tool to sanity-check their security claims. You can’t just say “it’s hard” anymore; you have to say “here’s the ceiling.”

Tom: So what’s the big picture? Where does this leave us? I think we need to bring in the bigger implications before we wrap up.

Jane: Let’s do that.

Conclusion: Tom: So we’re wrapping up our discussion of “The complexity of solving a system of equations of the same degree.” Jane, give us the final take.

Jane: The paper gives proven upper bounds on the degree of regularity and the solving degree for systems of equations of the same degree. That’s a direct handle on the complexity of solving them, which is the core security assumption in multivariate cryptography.

Tom: And the bounds are sharp, they apply to real schemes like the Cubic Simple Matrix encryption scheme, and they work even when the usual semiregular heuristic doesn’t apply.

Jane: Right. The method relies on the Eisenbud-Green-Harris conjecture, which is widely believed but not proven. So the results are conditional, but they’re still a big step forward because they replace heuristics with a proven ceiling.

Tom: And that ceiling tells you what security you can hope for. If you’re designing a scheme, you know the worst case, so you can choose your parameters accordingly.

Jane: And for the rest of us, it’s a reminder that a lot of cryptography rests on assumptions that are hard to verify. This paper gives us a way to verify at least one of those assumptions, at least up to a known conjecture.

Tom: So we’re saying goodbye to this paper, but not to the ideas in it. The bounds are going to be useful for anyone designing or analyzing multivariate schemes.

Jane: Absolutely. And we’ll be watching to see if anyone tightens these bounds or extends them to systems with mixed degrees.

Tom: That’s a good note to end on. Thanks for joining us, and we’ll see you next time with a fresh paper from arXiv.

Jane: Take care, everyone.

Giulia Gaggero, Elisa Gorla

armasuisse

cs.CR, math.AG, math.CO

Submitted: 2026-08-10

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 48/100

Key concepts

Degree of Regularity: This concept determines the complexity or 'breaking point' of a polynomial system. It is an upper bound on how hard it is to solve the system, and knowing this provides a concrete measure of security for cryptographic schemes.
Multivariate Cryptography: The security of these cryptographic systems relies on the assumption that solving large systems of equations is infeasible. The paper helps quantify this assumption by providing proven bounds on the complexity.
Eisenbud-Green-Harris Conjecture: This is a well-known conjecture in commutative algebra used in the paper's method. It allows researchers to reduce the problem of bounding system complexity to studying highly structured ideals called lex-plus-powers ideals.

Terminology

Core — 3× in this paper · explained in 2 episodes
Unbalanced Oil and Vinegar — 3× in this paper

Summary

Summary

This paper establishes upper bounds on the degree of regularity and the solving degree of polynomial systems consisting of equations of the same degree, under the assumption that the degree of regularity is finite. These bounds translate into upper bounds on the complexity of solving such systems via Gröbner basis methods. The bounds depend on the number of equations, the number of variables, and the degree of the equations.

The paper considers systems for which the degree of regularity is finite, which are exactly the systems for which the approach via the degree of regularity provides a non-trivial complexity bound. For polynomials in n variables, the degree of regularity is finite if and only if the ideal generated by the top-degree part of the system contains a regular sequence of n polynomials. For a system of polynomials of the same degree D, the degree of regularity is finite if and only if the regular sequence may be found in degree D.

The main results are conditional on Conjecture 22, the Eisenbud-Green-Harris Conjecture, an extensively-studied conjecture from commutative algebra. However, the bounds are proven and do not rely on any heuristic assumption. In particular, they apply to situations where no semiregular sequence exists.

The paper introduces the concept of a system being regular in degree D, meaning that the ideal generated by the top-degree parts of the system contains a regular sequence of n polynomials of degree D. It is shown that if a system is regular in degree D, then it has finite degree of regularity. The paper also notes that every cryptographic semiregular system is regular in some degree, but the converse does not hold.

The first main result, Theorem 25, provides an explicit upper bound for the degree of regularity of a system of polynomials that is regular in degree D. The bound is given in terms of the number of variables n, the number of equations m, and the degree D of the equations. The theorem states that if F = f1,..., fm ⊆ R is a polynomial system with f1top,..., fmtop linearly independent of degree D, and if dreg(F) < +∞, then dreg(F) ≤ (D - t) + (n - k)(D - 1), where k and t are determined by the interval in which m - n lies, with σk,t defined as a specific sum of binomial coefficients. The bound is sharp for all values of m, n, D, and is met by any system whose top-degree part is a (D,..., D; D)-LPP ideal.

Corollary 29 translates this into an upper bound on the solving degree for mutant algorithms: solv. degm(F) ≤ D - t + 1 + (n - k)(D - 1).

The paper also addresses systems to which the field equations are added, which is especially relevant when the degree D of the equations is at least the field size q. Proposition 33 handles very overdetermined systems where the top-degree parts are too many to be linearly independent modulo (x1q,..., xnq). In this case, the degree of regularity is exactly D, and the solving degree bounds are solv. degs ≤ 2D - 2 and solv. degm ≤ D + 1.

The second main result, Theorem 35, provides an upper bound for the degree of regularity of a system F ∪ x1q - x1,..., xnq - xn, where F is a system of m equations of degree D with q ≤ D ≤ n(q - 1). The bound is given in terms of the parameters k and t, which are determined by the interval in which m lies, with ςk,t defined as a sum of ηk,t terms, where ηk,t is a specific alternating sum of binomial coefficients. The theorem states that dreg(F ∪ x1q - x1,..., xnq - xn) ≤ B - 1 in certain special cases (when m = ςk,t and specific conditions on D and t hold), and dreg(F ∪ x1q - x1,..., xnq - xn) ≤ B in all other cases, where B = q - t + (n - k)(q - 1). Corresponding bounds on the solving degree are also provided.

Corollary 36 specializes Theorem 35 to the case of binary equations over F2, giving simpler formulas. The paper applies these results to the Cubic Simple Matrix encryption scheme, obtaining dreg ≤ 2n - 1, and to Unbalanced Oil and Vinegar (UOV) schemes, obtaining bounds on the degree of regularity.

The paper notes that the bounds are less tight than those obtained by assuming a system is semiregular, but they have the advantage of being provable, as they only require that the degree of regularity is finite and do not rely on the heuristic assumption that the system is semiregular.

Improvements for AI systems

Based on the paper, here are specific improvements that can be made to AI systems, particularly those involved in algebraic cryptanalysis, symbolic computation, and automated theorem proving:

Current limitation: AI-driven Gröbner basis solvers (e.g., in SageMath, Magma) rely on heuristic estimates (e.g., assuming semiregularity) to predict solving time, which can be wildly inaccurate.
Improvement: Integrate Theorem 25 and Theorem 35 as a pre-computation step. The AI system can now compute a proven upper bound on the degree of regularity (and hence solving degree) for any system of equations of the same degree, without assuming semiregularity. This allows the system to:
Automatically decide whether a given system is feasible to solve within a time/memory budget.
Choose the optimal algorithm (standard vs. mutant) based on the bound.
Provide a certified worst-case complexity estimate to the user, rather than a heuristic one.
Current limitation: Designers of multivariate schemes (e.g., UOV, Rainbow, Cubic Simple Matrix) often guess security parameters based on heuristic or experimental data.
Improvement: Use Corollary 29 and Corollary 36 to automatically compute the proven upper bound on the degree of regularity for a given parameter set (n, m, D, q). The AI system can then:
Reject parameter sets where the bound is too low (i.e., insecure).
Optimize parameters to maximize the proven bound, given constraints on key size and signature size.
Generate a security proof certificate for a proposed scheme, which is valuable for standardization.
Current limitation: AI systems often treat all polynomial systems uniformly, missing structural simplifications.
Improvement: Implement a module that checks the conditions of Proposition 13 (e.g., whether the top-degree part is zero-dimensional) and Lemma 32 (linear independence modulo field equations). Based on this, the system can:
Automatically reduce a system to a smaller equivalent one (e.g., by assigning random values to variables, as suggested in the paper).
Detect when the system is regular in degree D and apply the sharp bounds from Theorem 25 directly, avoiding unnecessary Gröbner basis computations.
For systems with D ≥ q, automatically add field equations and apply Theorem 35, which often yields tighter bounds than solving the original system.
Current limitation: MutantXL and similar algorithms use a fixed heuristic for when to switch to mutant strategy.
Improvement: Use Theorem 4 and the bounds from Theorems 25 and 35 to determine a priori the maximum degree at which mutants will appear. The AI system can then:
Pre-allocate memory for Macaulay matrices up to that degree, avoiding dynamic resizing overhead.
Decide whether the mutant strategy is worth employing at all, based on the gap between the bound and the degree of the equations.
Dynamically switch between standard and mutant algorithms mid-computation, guided by the proven bounds.
Current limitation: When an AI system claims to have broken a cryptosystem via algebraic attack, the claim is often based on empirical timing, which is not reproducible or provable.
Improvement: The AI system can now output a proof of the attack's complexity: The solving degree is at most X, therefore the attack requires at most Y bit operations. This is done by:
Verifying the conditions of Theorem 25 or Theorem 35 (e.g., checking linear independence of top-degree parts).
Computing the explicit bound B.
Applying Theorem 3 or Theorem 4 to convert the degree bound into a bit-complexity bound.
Generating a human-readable certificate that can be independently verified.
Current limitation: AI systems for symbolic computation rarely test open conjectures like the Eisenbud-Green-Harris Conjecture (Conjecture 22) on random instances.
Improvement: Build a search engine that generates random systems satisfying the hypotheses of Theorem 25 and Theorem 35, computes the actual degree of regularity (for small n, D, q), and compares it to the bound. This can:
Provide empirical evidence for or against Conjecture 22 in the specific cases used in cryptography.
Automatically flag any counterexample found, which would be a major research contribution.
Help refine the bounds for specific parameter ranges (e.g., D close to q).
Current limitation: Tools like CryptoMiniSat or SageMath's groebner function do not automatically choose the best strategy based on proven bounds.
Improvement: Create a wrapper that:

Takes a system of equations.
Checks if all degrees are equal (if not, homogenizes or splits).
Computes the bound from Theorem 25 (if D < q) or Theorem 35 (if D ≥ q).
If the bound is below a user-specified threshold, runs the Gröbner basis computation with a guaranteed termination degree.
If the bound is too high, reports infeasibility before attempting computation, saving hours of wasted CPU time.

Given any system of m equations of degree D in n variables over Fq, output a certified upper bound on the solving degree and the bit-complexity of solving it, without any heuristic assumptions.
For a proposed multivariate cryptosystem, automatically compute the security level (in bits) based on the proven bound, and reject any parameter set where the bound is below a minimum security threshold.
For a given system, automatically decide whether to add field equations (if D ≥ q) and whether to use a mutant strategy, based on the proven bounds, rather than trial-and-error.
Generate a machine-checkable proof that a specific algebraic attack on a cipher requires at most X bit operations, which can be submitted as evidence in security evaluations.
For researchers, automatically search for counterexamples to Conjecture 22 in the specific cases relevant to cryptography, potentially leading to a disproof or a refinement of the bounds.
For AI-driven symbolic computation frameworks, provide a certified mode where all complexity estimates are proven, not heuristic, enabling safe use in critical applications (e.g., financial cryptography, military communications).

These improvements directly leverage the paper's main contributions: sharp, proven upper bounds on the degree of regularity for systems of equal-degree equations, with and without field equations, and the translation of those bounds into solving-degree and bit-complexity estimates.

Abstract

Many systems of interest in cryptography consist of equations of the same degree. Under the assumption that the degree of regularity is finite, we prove upper bounds on the degree of regularity of a system of equations of the same degree, with or without adding the field equations to the system. The bounds translate into upper bounds on the solving degree of the systems, and hence on the complexity of solving them via Gr"obner bases methods. Our bounds depend on the number of equations in the system, the number of variables, and the degree of the equations.