Security Pitfalls

Jun 2026

Massimo Ostuzzi

In this story of the month, I want to share my first attempt at designing a signature scheme which, well, did not turn out the way I had hoped. Along the way, we will take a closer look at the hardness assumption that was the subject of my previous story of the month.

Hard Problems From Many Equations in Many Variables
Public-key cryptography is built on so-called hardness assumptions, i.e. the belief that a particular problem cannot be solved efficiently. For now, our goal is to understand one of these difficult problems and see how it can be used to build a cryptographic signature scheme.

Anyone who has studied a little math has come across equations. An equation is simply a mathematical expression relating some unknown quantities to some known ones. For example, in x + 2 = 3 the unknown quantity is denoted by x. This equation is very easy to solve: its unique solution over the integers is x=1. A slightly more complicated example is x²-3x+2=0. What makes this one less obvious is that the unknown appears quadratically (the exponent is 2) rather than linearly, as it did before. In general, the higher the degree of an equation, the harder it is to solve. Fortunately, degree 2 is as far as we need to go here.

But that is not the end of the story. Two further complications come into play. First, we are interested in systems of equations in many variables. Second, the solutions we care about do not live in the ordinary number systems we are used to, but in finite fields. Once we add these two ingredients, finding solutions becomes extremely hard and, in fact, it is NP-hard.

Public-key cryptography needs asymmetry
Even so, we are not quite there yet. Public-key cryptography is also known as asymmetry cryptography, because a fundamental ingredient of the underlying hard problem is asymmetry. In our setting of multivariate quadratic (MQ) equations, this asymmetry traditionally arises from a special class of systems. Let me give an example:

Consider the MQ system

where t₁,t₂ are two fixed numbers. This system is easy to solve with the following trick. First, fix x₃ randomly, say fix to x₃=1, and substitute it into the equations. Now the system becomes linear in the remaining free variables

and linear systems are notoriously easy to solve. The problem is that, used as is, this system can be solved just as easily by any user. To create the asymmetry, the idea is to perform a change of variables. In plain terms, we obfuscate the special shape of the system by relabelling the variables so that it looks random. Afterwards, only the user who built the original MQ system can solve it efficiently, while everyone else is left facing a generic-looking system. This works as long as recovering the change of variables is itself hard enough, and that is precisely the hardness assumption we were searching after.

This hardness assumption has withstood all cryptanalytic efforts and the signature schemes based on it are nowadays believed to be secure.

What is the broad idea of the technique?
The recipe is now clear: start with an MQ problem that is easy to solve, then obfuscate its structure with a change of variables. Together with a colleague, I started a project built on a different choice of easy-to-solve MQ system.

Again, let us work with an example.

Consider the MQ system

This one is easy to solve because of its layered structure. You can begin by solving the first equation for x₁, which is straightforward since it involves only one variable. Once x₁ is fixed, the second equation depends on the single variable x₂, which is again easy to solve. And once x₂ is fixed as well, the last equation involves only the one variable x₃, so it is easy to solve, too.

Why is this a good idea?
The standard construction I described earlier has a structural limitation caused by certain known attacks: the number of variables must be at least roughly three times the number of equations to remain secure. This inflates the size of the public keys and signatures, making it less size-efficient. Our construction avoided this limitation, which let us work with smaller MQ systems while reaching the same level of security.

Security Pitfall
After a few weeks of cryptanalysis, my colleague and I were starting to feel confident about the security of our construction. We had a neat attack idea that seemed clever and even gave us a criterion for choosing the size of our MQ systems. One evening, I was relaxing on the sofa, mulling over the day that had just passed. We had enjoyed cryptanalysing the construction and felt pleased with our progress. A little bored, I began preparing an exercise class on dual codes for the cryptanalysis course. Suddenly, it clicked: could the very idea behind dual codes be turned into an attack on our own construction? A few minutes of thought were enough to convince me, unfortunately, that our new MQ-based construction was broken. The next day, after I explained the attack to my colleague, we searched the literature and found that it was a well-known family of attacks called MinRank attacks. We spent a few more hours trying to repair our idea, but to no avail.

Lesson Learnt
Even though the project did not work out in the end, we both came away with a much deeper understanding of MQ-based cryptography and gained our first real experience with cryptographic constructions. And, of course, we also became thoroughly acquainted with that very annoying MinRank technique.

To conclude, I want to reflect on the value of teaching and of stepping outside your comfort zone. Had I not needed to prepare that session on dual codes, I would most likely have missed this elegant (yet rather inconvenient for us) attack.