Full-Key Recovery and Forgery from One MQOM v2.1 Signature

Imagine you are trying to send a secret message to a friend, but you live in a world where super-fast computers (called quantum computers) might one day exist. These future machines could break most of the locks we use today to keep our secrets safe. To prepare for this, scientists are building new, super-strong digital locks called "post-quantum signatures." Think of these like a special kind of wax seal on a letter. Even if a thief has a magic hammer that can smash normal locks, this new wax seal is made of a material that should hold up.

One of the most promising new locks being tested is called MQOM. It works a bit like a giant, complex puzzle. To sign a letter, the sender uses a secret "witness" (a hidden key) to solve a math problem involving many variables. To prove they solved it without showing the secret, they use a clever trick called "MPC-in-the-head." Imagine the sender pretending to be a whole team of people, each holding a tiny piece of the secret. They play a game where they reveal just enough to prove the team solved the puzzle together, but not enough to reveal the actual secret pieces. If the math holds up, the signature is valid. We care about this because if these new locks have a hidden crack, our future digital safety could crumble before we even get there.

Now, let's talk about the story in this paper. A researcher named José Luis Delgado looked closely at a specific version of this MQOM lock (version 2.1) and found a surprisingly simple way to break it. The paper argues that if an attacker gets just one valid signature from the system, they can figure out the entire secret key and forge new signatures for any message they want. It's like if a thief saw you open your front door once, and that single peek was enough for them to build a master key that opens every lock in your house.

Here is how the "magic trick" works, explained through a story. Imagine the secret key is a long, hidden treasure map. The MQOM system hides this map inside a giant tree made of branches. When you sign a message, the system shows you a path up the tree to a specific hidden leaf (a spot on the map), but it keeps the leaf itself covered. However, it also gives you a "sibling path"—a list of the branches next to the hidden leaf. Because of how the tree is built, if you know the branches next to the leaf, you can figure out exactly what the hidden leaf would be if you knew a small prefix of the secret map.

The paper discovered that the system also leaves a "commitment," which is like a sealed envelope containing the hidden leaf. The researcher realized that by combining the sibling path (the branches) with the sealed envelope, they could write down a single, giant equation. This equation has one unknown: the small prefix of the secret map. The attacker doesn't need to guess the whole map; they just need to solve this one equation to find that small prefix.

Once they find that prefix, the signature they already have gives them a "correction suffix"—a little note that says, "Here is the rest of the map to go with the prefix you just found." By sticking the prefix and the note together, the attacker reconstructs the entire secret map (the full signing key). With this key, they can sign any new message, and the system will accept it as real.

The paper doesn't just guess this works; they actually did the math and the computer work to prove it. They calculated exactly how much computing power it would take to solve this equation for the different strength levels of the lock (called Categories I, III, and V). They found that for all three categories, the effort required is less than the security limit NIST set for these locks.

For the easiest level (Category I), the attack takes about $2^{142.335112}$ operations. For the medium level (Category III), it takes about $2^{206.774558}$ or $2^{206.988685}$ operations, depending on how much of the map they scan. For the hardest level (Category V), it takes about $2^{271.794162}$ operations. In every case, the number of steps the attacker needs is lower than the number of steps the lock was supposed to require to be safe.

The researchers didn't just stop at the math. They built a computer program that actually ran the attack. They took a real signature, solved the equation, recovered the exact secret key byte-by-byte, and then used that key to sign a brand new message. The system's verifier checked the new signature and said, "Yes, this is valid!" This proved that the attack works in the real world, not just on paper.

The paper also looked at whether changing some settings would fix the problem. They found that simply adding a "salt" (a random number) to the process changes the numbers in the equation but doesn't stop the attack. The equation still exists; it just looks slightly different. To truly fix this, the designers would have to change how the tree path relates to the secret, how the leaf is committed, or how the correction note is generated.

In short, this paper shows that the current version of the MQOM lock has a hole big enough to walk right through. It turns a single signature into a master key, allowing an attacker to forge messages with less effort than the lock was designed to withstand. The author has shared their code and results so others can check their work, and they suggest that the designers of MQOM need to patch these specific parts of the system before it can be considered safe for the future.