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

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.