🔢 mathematics

Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

This paper presents a polynomial-time key-recovery attack that breaks all proposed parameter sets of the Enhanced Gabidulin Matrix Codes (EGMC) encryption scheme by combining combinatorial and algebraic techniques to recover an equivalent secret key, thereby reducing the claimed 128-bit security level to just 35 bits.

Original authors: Thai Hung Le

Published 2026-08-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Thai Hung Le

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 the internet as a giant, bustling city where everyone is trying to send secret messages. To keep these messages safe from prying eyes, we use digital locks called encryption. For a long time, scientists have been building these locks using complex math puzzles that are easy to create but incredibly hard to solve without the key. Recently, a new type of lock was proposed using a special kind of math involving grids of numbers and "rank" (which is just a fancy way of measuring how much information is actually packed inside the grid). The creators of this new lock thought they had added a layer of "noise"—like static on a radio—to hide the lock's true shape, making it look like a random mess to anyone trying to break in. They claimed this new design was so secure that even a super-fast quantum computer couldn't crack it, and they promised it would be tiny and efficient, perfect for the future of secure communication.

However, just like a magician's trick that relies on a specific sleight of hand, this new lock had a hidden flaw. A researcher named Thai Hung Le discovered that the "noise" wasn't actually hiding the secret shape as well as everyone thought. By using a clever mix of guessing and algebraic detective work, the researcher found a way to peel back the layers of static and reveal the original, hidden structure underneath. It's as if someone built a house of cards with a secret blueprint, covered it in fog, and then realized that if you just looked at the fog from the right angle, the blueprint was still faintly visible. This discovery is a big deal because it means the new locks aren't as safe as advertised, and the people who designed them need to rethink their blueprints before they start using them to protect our data.

The Paper's Big Discovery

In this paper, Thai Hung Le presents a new way to break the "Enhanced Gabidulin Matrix Code" (EGMC) encryption schemes. These schemes were introduced recently as a way to create very small, efficient encryption keys that could survive attacks from future quantum computers. The security of these schemes relied on the idea that if you took a special, structured grid of numbers and added random rows and columns to it (the "noise"), it would become impossible to tell the difference between the real code and a completely random mess.

The author shows that this assumption is wrong. Instead of trying to brute-force every possible way to remove the noise (which would take forever), the paper introduces a "hybrid" attack. Imagine you are trying to find a specific pattern in a giant, scrambled mosaic. The old way was to guess the position of every single tile. This new method is smarter: it guesses the position of just one row of tiles, and then uses math to instantly figure out where the rest of the tiles must be.

The paper details two main ways to do this:

Guessing the Columns: The attacker guesses how the columns of the grid were shuffled and then uses algebra to solve for how the rows were shuffled.
Guessing the Rows: The attacker guesses how the rows were shuffled and then solves for the columns.

Once the attacker figures out the shuffling, they can strip away the random noise and reveal the original, hidden structure. The paper proves that this structure is a "Gabidulin code," which is a type of math puzzle that is actually quite easy to solve once you know the secret pattern.

What the Paper Actually Breaks

The author doesn't just find a tiny crack; they smash the whole window. The paper demonstrates that this attack works against all 16 of the proposed parameter sets for the EGMC encryption schemes. This means every version of the lock that was suggested for use is now considered broken.

To give you a sense of how effective this is, the paper looks at a specific set of numbers that was supposed to offer 128-bit security (a standard level of safety). The author shows that their attack reduces this security level down to just 35 bits. In the world of encryption, that's like going from a vault with a million-digit combination to a lock that a child could pick in seconds.

The paper provides a concrete example of this power: using their method, the researchers were able to recover the secret key for that 128-bit security level in less than 10 minutes. This wasn't just a theoretical idea; they actually built a computer program to do it.

What the Paper Rules Out

It is important to note what this paper says doesn't work. The author explains that previous attempts to break these codes relied on "combinatorial" methods, which involve guessing both the row and column shuffles at the same time. The paper argues that this old way is too slow and inefficient compared to their new "hybrid" approach.

Furthermore, the paper argues against the idea that simply making the parameters bigger (adding more noise) will fix the problem for all cases. The author shows that for certain types of these codes—specifically when one of the noise factors (either the number of extra rows or the number of extra columns) is zero—the attack becomes so fast that it runs in "polynomial time." This means that no matter how much you increase the size of the lock in those specific cases, the attack will still be fast enough to break it. The only way to potentially fix this, the paper suggests, would be to change the fundamental design so that both noise factors are non-zero and large enough to stop the attack, but the author warns that this might make the keys and messages too big to be useful.

How Sure Are They?

The paper is very confident in its results. The author didn't just guess; they provided a full mathematical proof of how their attack works and backed it up with a working computer implementation. They explicitly state that their attack breaks all proposed versions of the scheme. They also compare their results to previous attacks, showing that their method is significantly faster and more powerful. The paper concludes that the EGMC encryption schemes are no longer safe for use, and the security community needs to move on to different designs.

Technical Summary: Breaking ACDGV MinRank Gabidulin Encryption Schemes over Matrix Codes

Problem Statement
The paper addresses the security of Enhanced Gabidulin Matrix Codes (EGMC), a masking scheme introduced by Aragon et al. at Asiacrypt 2024. EGMC was designed to conceal the algebraic structure of Gabidulin matrix codes, enabling compact McEliece- and Niederreiter-type encryption schemes with small ciphertexts (e.g., 65 bytes for 128-bit security). The security of EGMC relies on the Decisional EGMC-Indistinguishability problem: the assumption that a masked EGMC code is computationally indistinguishable from a random matrix code. Previous cryptanalysis, specifically a MinRank-based kernel attack by Porwal et al. (Eurocrypt 2026), demonstrated exponential-time attacks that broke a subset of the proposed parameter sets but left others secure. The author investigates whether the EGMC construction retains sufficient hidden structure to be broken more efficiently.

Methodology
The author proposes a new "hybrid" distinguisher and a subsequent key-recovery attack that combines combinatorial guessing with algebraic solving. Unlike previous distinguishers that brute-force both row and column compression matrices, this attack guesses only one compression matrix and solves for the other using algebraic techniques.

The attack operates in two primary directions:

Guess- $V$ -solve- $U$ : The attacker guesses a column compression matrix $V$ and algebraically solves for a row compression matrix $U$ .
Guess- $U$ -solve- $V$ : The attacker guesses a row compression matrix $U$ and solves for a column compression matrix $V$ .

Algebraic Modeling and Solving
Once a valid compression matrix is guessed, the public code is compressed into a subspace equivalent to a short Gabidulin code (specifically a $[k+1, k]$ code). The author models the condition that this compressed code must be an $F_{q^m}$ -hyperplane annihilated by a specific vector. This leads to a system of bilinear equations which, upon linearization, yields a homogeneous linear system over the extension field $F_{q^m}$ .

The core of the attack involves finding a rank-1 solution within the kernel of this linear system. The author observes that the kernel admits a basis with entries in the base field $F_q$ . Consequently, the problem reduces to finding a linear combination of these basis matrices that results in a rank-1 matrix. This is formulated as a system of quadratic equations (vanishing $2 \times 2$ minors).

To solve this quadratic system efficiently, the author employs the eigenvalue method (Stickelberger-Eigenvalue method) for zero-dimensional polynomial systems. They leverage the Frobenius stability of the kernel to perform computations over the smaller field $F_q$ rather than $F_{q^m}$ , significantly reducing complexity. A key conjecture (Conjecture 1) posits that the quotient algebra of the ideal generated by the minors has a dimension equal to $m$ , ensuring the system is zero-dimensional and solvable via eigenvalues.

Key Contributions

Hybrid Distinguisher: The paper introduces a distinguisher that avoids the full brute-force cost of previous methods by solving for one compression matrix algebraically.
Polynomial-Time Key Recovery: The author demonstrates that if either of the appending factors $\ell_1$ or $\ell_2$ is zero, the attack becomes polynomial-time. This is because the exponential guessing factor vanishes, leaving only the algebraic solving step, which recovers the hidden compression matrix efficiently.
Code Extension: Upon recovering a punctured (short) Gabidulin code, the author provides a polynomial-time algorithm to extend this code back to a full-length equivalent secret Gabidulin code by exploiting the $q$ -Frobenius structure of Gabidulin codes.
Universal Decryption: The recovered equivalent secret key (trapdoor) allows for the decryption of both EGMC-McEliece and EGMC-Niederreiter ciphertexts.

Results
The attack breaks all 16 proposed parameter sets for EGMC-Niederreiter encryption schemes.

Security Reduction: For the parameter set targeting 128-bit security with parameters $(2, 17, 37, 4, 0)$ , the attack reduces the security level from a claimed 186 bits to approximately 35 bits.
Efficiency: In the author's implementation, the equivalent secret key for the 128-bit parameter set is recovered in less than 10 minutes.
Comparison: The attack outperforms previous best attacks (combinatorial and MinRank-based) by large margins, as shown in Table 1 of the paper.

Significance and Claims
The paper claims that the EGMC construction, as proposed, fails to provide post-quantum security for the specific parameter families where $\ell_1 = 0$ or $\ell_2 = 0$ . The author argues that simply increasing parameters without changing the masking construction does not restore security for these families, as the algebraic solving step remains polynomial-time.

The author notes that a potential repair would require keeping both $\ell_1$ and $\ell_2$ non-zero and sufficiently large to ensure the minimum of the two attack directions exceeds the target security level. However, they caution that increasing these parameters directly increases the public key and ciphertext sizes, and it remains to be investigated whether such a repair would remain competitive with other code-based schemes. The paper concludes that the current EGMC parameters are insecure and that the proposed attack provides both a distinguisher and a full key-recovery mechanism.

The Paper's Big Discovery

What the Paper Actually Breaks

What the Paper Rules Out

How Sure Are They?

More like this