Pith. sign in

REVIEW 4 major objections 4 minor 13 references

Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A hybrid algebraic-combinatorial attack recovers an equivalent secret key for all 16 EGMC encryption parameter sets, cutting the 128-bit set from 186 to 35 bits of security.

desk verdict Plausible new attack on EGMC, but the 'breaks all 16' claim leans on an unproved quotient-dimension conjecture; deserves referee time. read the letter →

arxiv 2608.03328 v1 pith:36HWBJUX submitted 2026-08-04 cs.CR cs.ITmath.IT

Thai Hung Le This is my paper · ORCID
classification cs.CRcs.ITmath.IT MSC 94A6011T7113P1094B05
keywords cryptanalysisGabidulincodesmatrixMinRankkeyrecoverydistinguisherGröbnerbasispost-quantumcryptography
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the EGMC masking construction—appending random rows and columns to a Gabidulin matrix code and scrambling with invertible matrices—leaves enough structure for an attacker to recover an equivalent trapdoor. The new attack guesses only one of the two compression matrices and solves algebraically for the other, reducing the problem to finding a rank-1 element in the Frobenius-stable kernel of a linear system. Once a short punctured Gabidulin code is exposed, the full-length equivalent secret key is recovered in polynomial time. If correct, all 16 proposed EGMC parameter sets are broken; the claimed 128-bit set (2,17,37,4,0) drops from 186 to 35 bits of security, with key recovery demonstrated in under 10 minutes.

What carries the argument

The hybrid distinguisher: guess one compression matrix (V or U) and solve for the other algebraically rather than guessing both. The solving step linearizes the bilinear equations expressing that the compressed code lies in an F_{q^m}-hyperplane; the kernel is Frobenius-stable, and the rank-1 solutions that correspond to valid (h,u) pairs are extracted by the eigenvalue method on the quotient A = F_q[$\alpha$]/I, where I is generated by all 2x2 minors of the kernel matrix. The claimed costs (15)–(17) rely on Conjecture 1 that dim_{F_q} A = m.

What would settle it

For a valid guess V on the 128-bit parameter set (2,17,37,4,0), compute the quotient A=F_2[alpha]/I where I is generated by the 2x2 minors of the rank-1 kernel matrix W(alpha). If dim_{F_2} A is ever greater than m=37, Conjecture 1 fails and the Phase 3 extraction cost in (15) is underestimated, invalidating the claimed 35-bit security level.

Watch

Extended reading notes

Core claim

The central claim is that the Enhanced Gabidulin Matrix Code (EGMC) construction is not a secure masking: an attacker can distinguish an EGMC public code from a random matrix code and recover a code equivalent to the secret Gabidulin code. The attack guesses a column compression V (or, in the reverse direction, a row compression U) and models the condition that the compressed code is annihilated by an F_{q^m}-hyperplane, producing a bilinear system whose linearization has a Frobenius-stable kernel. A rank-1 kernel matrix factors into the missing compression and hyperplane vector; the resulting [k+1,k] Gabidulin puncture is then extended to a full-length equivalent key using the q-Frobenius s

Load-bearing premise

The cost formulas assume the quotient algebra A=F_q[alpha]/I generated by the 2x2 minors has dimension exactly m over F_q and that the EGMC assumption a_m(V)=1 holds; the paper proves only dim A >= m and gives a heuristic upper bound, so if the true dimension is larger the claimed security reductions lose their support.

Editorial extensions

If this is right

  • EGMC-McEliece and EGMC-Niederreiter cannot be used with their proposed parameters; all 16 parameter sets are broken by the attack.
  • The claimed 128-bit parameter set (2,17,37,4,0) offers only about 35 bits of security, and an equivalent secret key is recovered in less than 10 minutes.
  • When ell1=0 or ell2=0 the attack is polynomial-time, so increasing parameters alone does not restore security for those families; any repair must keep both ell1 and ell2 nonzero and large enough.
  • The distinguisher applies to any F_{q^m}-linear code hidden by the same random rows-and-columns masking, not only to Gabidulin codes.
  • An equivalent trapdoor is sufficient for polynomial-time decryption of both EGMC variants, so the attack is a full key-recovery, not merely a distinguisher.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If Conjecture 1 holds in the full parameter range, the same rank-1 extraction strategy may transfer to other rank-metric masking schemes that hide an F_{q^m}-linear code by row/column extensions, widening the attack's scope beyond EGMC.
  • The polynomial-time regime suggests a design constraint for future matrix-code masks: both appended dimensions ell1 and ell2 must grow, and even then the minimum of the two attack directions in (17) is the real security ceiling.
  • The security estimates are conditional on a conjectured quotient dimension; an independent verification of dim_{F_q}A = m for the exact parameter sets (not only the small instances in the appendix) would settle the attack's true cost.
  • The random-subspace model behind Proposition 5 could be tested directly by sampling public codes, counting Frobenius orbits of rank-1 solutions, and checking whether a_1(V) is as small as predicted.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper presents a structural key-recovery attack against the Enhanced Gabidulin Matrix Code (EGMC) encryption schemes of Aragon et al. (Asiacrypt 2024). The attack is a hybrid distinguisher with two directions: guess-V-solve-U (§3.1) and guess-U-solve-V (§3.2). In each direction, one compression matrix is guessed, a bilinear system is linearized, and a rank-1 solution is extracted from the kernel using the eigenvalue method. The claimed cost is the minimum of the two directions, Eq. (17), with per-direction costs in Eqs. (15) and (16). The paper further shows how to extend a short punctured Gabidulin code to a full equivalent secret key (§4) and how to decrypt both McEliece and Niederreiter variants (§5). It reports that all 16 proposed EGMC parameter sets are broken, e.g., reducing the claimed 128-bit set (2,17,37,4,0) from 186 bits to 35 bits, with an implementation recovering an equivalent key in under 10 minutes. The central technical engine is Conjecture 1 in §3.1: the quotient A = F_q[α_1,...,α_{ρ-1}]/I generated by the 2×2 minors has dim_{F_q} A = m.

Significance. If the claimed attack is correct, it is a substantial advance: it provides both a distinguisher and a key-recovery attack against a recently proposed compact post-quantum encryption family, and it is polynomial-time when one of the masking parameters ℓ1 or ℓ2 is zero. That finding would invalidate the security estimates of all 16 proposed EGMC parameter sets and force a redesign of the masking construction. The paper is also valuable for its explicit combination of combinatorial guessing with algebraic rank-1 extraction, and for the reproducible experimental infrastructure (the code repository is referenced). However, the central security reduction is conditional on an unproved regularity conjecture (Conjecture 1), and the experimental validation covers only very small parameters (q=2, m≤7, k≤6, ℓ1,ℓ2≤2), far from the target sets (m=37,...,79). The significance is therefore high if the conjecture is true, but the current evidence does not yet establish the advertised 'breaks all 16' claim.

major comments (4)
  1. [§3.1, Conjecture 1 and Eq. (15)] The cost formula (15) for guess-V-solve-U is valid only if the quotient A = F_q[α_1,...,α_{ρ-1}]/I generated by the 2×2 minors has dimension exactly m and, moreover, the degree-2 Macaulay nullity is already m without higher-degree growth. Section 6 establishes only the lower bound dim A ≥ m (Proposition 4). Proposition 5 gives an upper bound on Pr[dim A > m] only under a random-subspace model for P(L0(V)) and under the 'EGMC assumption a_m(V)=1' stated in §6.2, which is essentially the content of Conjecture 1. If dim A > m for any target parameter set, the eigenvalue extraction may return additional rank-1 points that are not multiples of the hidden full-rank U, and the true cost of Phase 3 is not the binomial expression in (15). The advertised reductions in Table 1 are therefore not established by the present arguments.
  2. [§6.2, Proposition 5 and a_m(V)=1] Proposition 5 is the only quantitative control on unwanted solutions, but it explicitly assumes (a) m is prime, which holds for the proposed sets, and (b) the hidden orbit is the only size-m Frobenius orbit in S(V), i.e., a_m(V)=1. This latter assumption is not derived; the text calls it 'the EGMC assumption'. Since a_m(V)=1 is essentially a restatement that the rank-1 solution set has exactly the hidden orbit of size m, it is very close to assuming Conjecture 1 rather than providing independent support. The proof also relies on the random-subspace model for P(L0(V)) and on the equality r0=r, which assumes A(V) has full row rank. The resulting Markov bound (14) is a heuristic, not a proof. This is load-bearing because the success probability of the algebraic step for the actual parameter sets is not otherwise quantified.
  3. [Appendix A and target parameters] The experimental evidence for Conjecture 1 covers only q=2, m≤7, k≤6, ℓ1≤2 (Appendix A), and the guess-U-solve-V diagnostics in Appendix B are similarly restricted. The target parameter sets in Table 1 have m up to 79, k up to 71, and ℓ1,ℓ2 up to 5. No extrapolation argument is given to show that the degree-2 nullity behavior observed for m≤7 persists at these sizes. Since the central claim 'breaks all 16 parameter sets' is obtained by evaluating (15) and (16) under Conjecture 1, the evidence is far from the regime where the claim is made. The paper should either prove the conjecture for the relevant parameter ranges or provide convincing computational evidence at substantially larger parameters.
  4. [§7, Eqs. (15)–(17)] The complexity estimates use ω=2.8 and omit all multiplicative constants, presenting costs as log2 of estimated gate counts. This is acceptable for asymptotic comparison, but the paper reports precise bit-security reductions (e.g., 186→35 bits) that depend on the exact exponent in Eq. (15). The omission of constants is not the main issue; the issue is that the exponent itself is conjectural. Additionally, the final estimate is the minimum of the two directions, so the security reduction is only as strong as the weaker direction; for the ℓ2=0 rows the V→U direction becomes polynomial only under the same conjecture. The claim of 'less than 10 minutes' for one parameter set is from an implementation, but no implementation details, machine configuration, or success-rate statistics are given for that run, making it difficult to assess robustness.
minor comments (4)
  1. [§2.3, Definition 2] The text says '3km random matrices' but then lists three families of random matrices (R_i, R'_i, R''_i) for each of km basis elements, which is 3km matrices. The wording is slightly confusing; consider writing '3km random matrices in total'.
  2. [§3.1, Phase 3] The phrase 'the M nullity dimension is already m and remains m at higher degrees' is used to motivate Conjecture 1, but 'M nullity' is not formally defined. Please define the Macaulay nullity and state precisely which matrix is being used.
  3. [§6.2] The notation P(L0(V)) is used in the proof of Proposition 5 but is only implicitly defined. A formal definition of L0(V) and the projective-space notation would improve readability.
  4. [Appendix B, Table 3] In the table, the row for (q,k,m,ℓ2)=(2,4,5,2) appears to duplicate a row in Appendix A. If this is intentional for comparison, please say so; otherwise one of the entries may be mislabeled.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the attack is an external structural break; the load-bearing unproved Conjecture 1 is a correctness risk, not a circular reduction.

full rationale

The paper's central derivation—the hybrid distinguisher and key-recovery attack on EGMC—is self-contained and does not reduce to its own inputs. The attack equations (bilinear system (3), rank-1 condition (4), cost formulas (15)–(16)) are derived from the public code's dimensions and the masking transformation, not fitted to the target or defined in terms of the attack's success. No self-citation is load-bearing; the paper cites only the scheme paper, prior attacks, and standard algebra references. The only load-bearing unproven statement is Conjecture 1 (dim_Fq A = m), which is explicitly labeled a conjecture. Section 6's supporting argument (Proposition 5) assumes a_m(V)=1, which is essentially the same uniqueness content, so the support is conditional rather than a complete proof. This is an acknowledged, load-bearing unproved assumption and a genuine correctness risk for the claimed 'breaks all 16 parameter sets' costs, but it is not circularity: the paper does not disguise it as a derived theorem, and the attack's equations are not equivalent to the conjecture by construction. The experimental evidence covers only small parameters, making the extrapolation to the target sets heuristic, but again this is a verification gap, not a circular reduction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The attack rests on standard algebraic-geometry tools (eigenvalue theorem, Macaulay matrices, Frobenius orbits) plus three paper-specific heuristics: Conjecture 1 on the quotient dimension, a random-subspace model in Prop 5, and the structural assumption a_m(V)=1. There are no fitted numerical parameters and no newly invented physical or computational entities beyond the algorithmic objects of the attack itself.

assumptions (4)
  • ad hoc to paper Conjecture 1: dim_{F_q} A = m for the quotient A=F_q[α_1,...,α_{ρ-1}]/I generated by 2x2 minors.
    The polynomial-time rank-1 extraction via the eigenvalue method requires the quotient to be zero-dimensional of degree m. The paper provides empirical support (Appendix A) and partial bounds (Prop 4-5) but no proof; the attack's complexity estimates (15)-(16) rely on it.
  • domain assumption The random-subspace model for P(L0(V)) in the proof of Prop 5.
    Prop 5 bounds the probability that dim_Fq A > m by modeling the F_q-rational part of the kernel as a uniformly random projective subspace and counting rank-1 points via the Segre embedding. This is a heuristic model, not a proven property of EGMC matrices.
  • ad hoc to paper For a valid guess V, the hidden orbit is the only size-m Frobenius orbit in S(V), i.e., a_m(V)=1.
    Section 6.2 states this as an observed/assumed fact and calls it 'the EGMC assumption a_m(V)=1'; it is needed to conclude that Pr[dim A > m] is negligible, and it is not proven.
  • standard math Standard theorems: Finiteness Theorem and Eigenvalue Theorem for zero-dimensional ideals (Cox, Little, O'Shea).
    Used in Phase 3 to justify the eigenvalue extraction; standard background from [4,6].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes." pith.science (2026). https://pith.science/paper/36HWBJUX

@misc{pith2026260803328,
  author       = {Pith},
  title        = {Pith review of: Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/36HWBJUX}},
  note         = {Machine review of arXiv:2608.03328}
}
abstract

Enhanced Gabidulin Matrix Codes (EGMC), introduced by Aragon, Couvreur, Dyseryn, Gaborit, and Vincotte at Asiacrypt 2024, were designed to hide the algebraic structure of Gabidulin matrix codes while enabling very compact McEliece- and Niederreiter-type encryption schemes, with ciphertexts as small as $65$ bytes at the claimed 128-bit security level. Their security relies on the assumption that a masked EGMC code is hard to distinguish from a random matrix code. We show that this enhanced construction leaves enough structure for an equivalent code of the secret key to be recovered. Unlike previous cryptanalysis, our attack combines combinatorial and algebraic techniques to recover a Gabidulin-equivalent compressed code. This code can then be extended to a full-length equivalent secret key in polynomial time. As a result, the attack provides both a distinguisher and a key-recovery attack against the EGMC encryption schemes. The attack breaks all 16 proposed EGMC parameter sets by large margins. For example, for the claimed 128-bit parameter set $(2,17,37,4,0)$, it reduces the security level from 186 bits to 35 bits. In our implementation, the equivalent secret key is recovered in less than 10 minutes.

Figures

Figures reproduced from arXiv: 2608.03328 by the authors.

Figure 1
Figure 1. EGMC-McEliece encryption scheme 32 [PITH_FULL_IMAGE:figures/full_fig_p032_1.png] view at source ↗
Figure 2
Figure 2. EGMC-Niederreiter encryption scheme 33 [PITH_FULL_IMAGE:figures/full_fig_p033_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 10 canonical work pages

  1. [12]

    In: Advances in Cryptology - EUROCRYPT 2026 (2026), https://eprint.iacr.org/2025/1292, to appear

    Porwal, A., Wachter-Zeh, A., Loidreau, P.: Key attack on the acdgv matrix encryption scheme. In: Advances in Cryptology - EUROCRYPT 2026 (2026), https://eprint.iacr.org/2025/1292, to appear

    work page 2026

  2. [1]

    In: International Conference on the Theory and Application of Cryptology and Information Security

    Aragon, N., Couvreur, A., Dyseryn, V., Gaborit, P., Vinçotte, A.: Minrank gabidulin encryption scheme on matrix codes. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 68–100. Springer (2024) 27

    work page 2024

  3. [2]

    arXiv preprint arXiv:2011.04611 (2020)

    Couvreur, A., Debris-Alazard, T., Gaborit, P.: On the hardness of code equivalence problems in rank metric. arXiv preprint arXiv:2011.04611 (2020)

    arXiv 2011

  4. [3]

    In: International Conference on Post-Quantum Cryptography

    Couvreur, A., Zappatore, I.: An extension of overbeck’s attack with an application to cryptanalysis of twisted gabidulin-based schemes. In: International Conference on Post-Quantum Cryptography. pp. 3–37. Springer (2023)

    work page 2023

  5. [4]

    Springer (1997)

    Cox, D., Little, J., O’shea, D., Sweedler, M.: Ideals, varieties, and algorithms. Springer (1997)

    1997

  6. [5]

    In: Commutative Al- gebra: Expository Papers Dedicated to David Eisenbud on the Occasion of his 75th Birthday, pp

    Cox, D.A.: Stickelberger and the eigenvalue theorem. In: Commutative Al- gebra: Expository Papers Dedicated to David Eisenbud on the Occasion of his 75th Birthday, pp. 283–298. Springer (2021).https://doi.org/10.1007/ 978-3-030-89694-2_8

    work page 2021

  7. [6]

    Cox, D.A., Little, J., O’Shea, D.: Using Algebraic Geometry, Graduate Texts in Mathematics, vol. 185. Springer, 2 edn. (2005)

    work page 2005

  8. [7]

    Journal of combinatorial theory, Series A25(3), 226–241 (1978)

    Delsarte, P.: Bilinear forms over a finite field, with applications to coding theory. Journal of combinatorial theory, Series A25(3), 226–241 (1978)

    work page 1978

Show all 13 references
  1. [8]

    Journal of Symbolic Computa- tion16(4), 329–344 (1993).https://doi.org/10.1006/jsco.1993.1051

    Faugère, J.C., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero- dimensional Gröbner bases by change of ordering. Journal of Symbolic Computa- tion16(4), 329–344 (1993).https://doi.org/10.1006/jsco.1993.1051

    1993

  2. [9]

    In: 2nd International Sym- posium on Information Theory, 1973

    Gabidulin, E.: Combinatorial metrics in coding theory. In: 2nd International Sym- posium on Information Theory, 1973. Akademiai Kiado (1973)

    1973

  3. [10]

    In: International Workshop on Coding and Cryptography

    Loidreau, P.: A welch–berlekamp like algorithm for decoding gabidulin codes. In: International Workshop on Coding and Cryptography. pp. 36–45. Springer (2005)

    2005

  4. [11]

    Journal of cryptology21(2), 280–301 (2008)

    Overbeck, R.: Structural attacks for public key cryptosystems based on gabidulin codes. Journal of cryptology21(2), 280–301 (2008)

    2008

  5. [13]

    Percentage

    Seroussi, G., Roth, R.M.: On mds extensions of generalized reed-solomon codes. IEEE Transactions on Information Theory32(3), 349–354 (2003) 28 A Macaulay diagnostics for quadratic determinantal systems in guess-V-solve-Udirection Table 2: The rank and the number of columns of ...

    2003

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.