{"id":"72dece38-7523-47bd-abfd-db53c2ac807e","arxiv_id":"2608.03328","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A hybrid guess-and-solve algebraic attack recovers an equivalent Gabidulin decoding key for all proposed EGMC encryption parameter sets, cutting one 128-bit security claim to about 35 bits.","lead":"This paper breaks a proposed post-quantum encryption scheme (EGMC) whose ciphertexts can be as small as 65 bytes. The attack finds an equivalent secret key by guessing part of the masking matrices and solving algebraic equations for the rest, and it works on all 16 suggested parameter sets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Attack cost rests on unproved Conjecture 1 (dim A = m, degree-2 Macaulay nullity); experiments cover only m≤7, so the advertised security reductions for target sets are conditional.","rationale":"The reader identified Conjecture 1 and the associated a_m(V)=1 assumption as the weakest load-bearing premise. My stress-test confirms this is the single most important point: the attack's polynomial-time character and all Table 1 security reductions depend on the degree-2 Macaulay nullity being exactly m, and the paper proves only a lower bound dim A ≥ m. The only upper-bound argument relies on a random-subspace heuristic and on an assumption that is not proved. The appendix experiments are too small to cover the target parameter ranges. I found no internal contradiction in the reduction from EGMC to the rank-1 extraction, and the reported implementation on one parameter set is genuine supporting evidence; but it does not by itself establish the conjecture for all 16 sets. This is precisely the gap that makes the verdict conditional: the attack is plausible and likely correct, but the 'breaks all 16 parameter sets' wording is stronger than the current evidence. Since the reader already reached CONDITIONAL, my concern does not change the verdict; it reinforces it. An independent verification of the Macaulay nullity on the actual target sets, or a proof of Conjecture 1, would be the appropriate next step.","tokens_in":22293,"tokens_out":16615,"duration_ms":183657,"concrete_test":"For the claimed 128-bit set (q,k,m,ℓ1,ℓ2)=(2,17,37,4,0), take a random full-rank V∈F_2^{37×18}, build the kernel basis K_t from Eq. (3), form the normalized degree-2 Macaulay matrix M of the 2×2 minors as in §3.1 Phase 3, and compute nullity(M) over F_2. Check that nullity(M)=m=37, and then compute the degree-3 Macaulay block and check that its nullity is still 37. If either nullity exceeds 37, Conjecture 1 / the 2-regularity assumption behind Eq. (15) fails for a real target set. If both pass, repeat the same check on a set with ℓ1,ℓ2>0, such as (2,35,43,2,2), to validate the min in Eq. (17).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that all 16 EGMC parameter sets are broken with the costs in Table 1 rests entirely on Phase 3 of §3.1: the rank-1 extraction must have cost O( C(m+(k+1)ℓ1+1, 2)^ω ) in the V→U direction, and the analogous claim in §3.2 for U→V. Those formulas are valid only if Conjecture 1 holds: the quotient A = F_q[α_1,...,α_{ρ-1}]/I by the 2×2 minors has dim A = m and, moreover, the Macaulay nullity at degree 2 is already m and does not grow at higher degrees. Section 6 proves only dim A ≥ m (Proposition 4). The equality is supported by Proposition 5, but that proof assumes a random-subspace model for P(L0(V)) and explicitly invokes the unproved 'EGMC assumption a_m(V)=1' in §6.2, which is essentially the content of Conjecture 1. The empirical evidence in Appendix A covers q=2, m≤7, k≤6, ℓ1≤2 — far from the target sets (m=37,...,79, k up to 71). If dim A > m for any target set, or if the ideal requires Macaulay degree >2, then the exponent in Eq. (15) is not the true extraction cost and the eigenvalue method may return extra rank-1 points that are not the hidden full-rank U. Since the headline numbers (e.g., 186→35 bits for (2,17,37,4,0)) are obtained by evaluating (15) with ℓ2=0, an unproved extra orbit or higher regularity would invalidate the 'breaks all 16' claim, not merely its precision.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22762,"tokens_out":3250,"duration_ms":36465,"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":[{"comment":"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.","section":"§3.1, Conjecture 1 and Eq. (15)"},{"comment":"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.","section":"§6.2, Proposition 5 and a_m(V)=1"},{"comment":"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.","section":"Appendix A and target parameters"},{"comment":"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.","section":"§7, Eqs. (15)–(17)"}],"minor_comments":[{"comment":"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'.","section":"§2.3, Definition 2"},{"comment":"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.","section":"§3.1, Phase 3"},{"comment":"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.","section":"§6.2"},{"comment":"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.","section":"Appendix B, Table 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is potentially important, but the central claim rests on an unproved conjecture that is very close to the structural assumption the attack needs to break. The experimental support is limited to m≤7, while the advertised breaks are for m≥37. I would not recommend acceptance before Conjecture 1 is either proved for the relevant parameter ranges or supported by substantial computational evidence closer to the target sizes. If the conjecture is not established, the paper should be reframed as an attack conditional on a plausible algebraic regularity assumption, with the claimed security reductions explicitly marked as conditional."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The attack is real progress, but the headline numbers are conditional on a conjecture that the paper itself flags. If you work on code-based crypto, read it for the guessing-algebra hybrid and the polynomial-time Gabidulin extension; those are genuinely new and go well beyond the earlier Eurocrypt attack in [12]. The implementation is also shipped, which is a real plus.\n\nWhat the paper does well: it splits the attack into two directions (guess V, solve U; guess U, solve V), with the minimum of the two costs. The clever part is guessing only one compression matrix and reducing the other to a rank-1 extraction in a Frobenius-stable kernel. The punctured-code recovery in Section 4 is clean: a [k+1,k] code is extended to full length n in polynomial time, which is a nice structural observation. The reported experiments for small parameters match the theory, and the paper honestly labels its main assumption as Conjecture 1.\n\nWhere it is soft: Conjecture 1 (the quotient A has F_q-dimension exactly m) is load-bearing. The lower bound is proven, but the upper bound in Proposition 5 relies on a random-subspace model and an unproved 'EGMC assumption' a_m(V)=1 that is essentially the conjecture again. The empirical support covers m up to 7, while the target sets have m between 37 and 79. That is a big gap. If dimension is larger, or the ideal needs degree >2, the cost formulas in (15)-(16) and the claimed 186-to-35-bit reduction are not justified. Another minor point: complexity uses omega=2.8 and drops constants, which is fine for first-order estimates but not a security proof. The abstract's 'breaks all 16' is stronger than the evidence supports; 'reduces under Conjecture 1' is more accurate.\n\nOn balance, the central idea is sound and the gaps are addressable, not fatal. A referee should ask for either a proof of the conjecture (at least under plausible genericity assumptions) or validation on larger instances, and a clear statement of success probability for the actual parameter sets.\n\nThis paper deserves serious peer review. I would bring it to a reading group, and I would cite it (with the caveat) if I wrote about MinRank-based masking. Recommendation: send it to reviewers with expertise in commutative algebra and rank-metric cryptanalysis; desk rejection would be wrong.","headline":"Plausible new attack on EGMC, but the 'breaks all 16' claim leans on an unproved quotient-dimension conjecture; deserves referee time.","tokens_in":23165,"tokens_out":1573,"would_cite":true,"duration_ms":19690,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60","11T71","13P10","94B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["cryptanalysis","Gabidulin codes","matrix codes","MinRank","key recovery","distinguisher","Gröbner basis","post-quantum cryptography"],"falsifier":"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.","tokens_in":22158,"feed_emoji":"🔓","tokens_out":6717,"duration_ms":59779,"temperature":0.7,"pith_summary":"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.","feed_headline":"All 16 EGMC encryption sets broken by key-recovery attack","feed_subtitle":"128-bit target falls from 186 to 35 bits; equivalent secret key recovered in under 10 minutes.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the EGMC masking transformation, the two encryption schemes, and the security assumption the attack targets.","marker":"[1]"},{"why":"Supplies the left-stabilizer characterization used to identify and reconstruct the hidden F_{q^m}-linear structure.","marker":"[2]"},{"why":"Provides the eigenvalue method (Stickelberger) used to extract rank-1 kernel points from the quotient algebra.","marker":"[6]"},{"why":"Welch–Berlekamp-like decoding for Gabidulin codes is what makes the recovered equivalent trapdoor decrypt ciphertexts.","marker":"[10]"},{"why":"Overbeck's Frobenius-sum distinguisher is the structural baseline the attack extends to recover the punctured Gabidulin code.","marker":"[11]"},{"why":"The previous MinRank kernel key-recovery attack that broke 5 of 16 parameter sets, the baseline the new attack must beat.","marker":"[12]"},{"why":"Supports the idea that a short punctured code can be extended while preserving the MDS property, though Gabidulin structure allows extension to full length n.","marker":"[13]"}],"fun_headline_variants":["EGMC encryption cracked: 186-bit security drops to 35","Key recovery attack breaks all 16 EGMC parameter sets","Matrix-code encryption scheme falls to combined algebraic attack","EGMC hides structure, but not enough: full key recovery in minutes","New attack recovers EGMC secret key, shattering 128-bit claim"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["EGMC encryption cracked: 186-bit security drops to 35","Key recovery attack breaks all 16 EGMC parameter sets","Matrix-code encryption scheme falls to combined algebraic attack","EGMC hides structure, but not enough: full key recovery in minutes","New attack recovers EGMC secret key, shattering 128-bit claim"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00075,"raw_usage":{"total_tokens":3192,"prompt_tokens":777,"completion_tokens":2415,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":2327}},"tokens_in":521,"tokens_out":2415,"duration_ms":16930,"temperature":1.0,"reasoning_tokens":2327,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T20:53:46.451168+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"In: International Conference on the Theory and Application of Cryptology and Information Security","cited_arxiv_id":null,"evidence_quote":"Defines the EGMC masking transformation, the two encryption schemes, and the security assumption the attack targets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the eigenvalue method (Stickelberger) used to extract rank-1 kernel points from the quotient algebra."},{"cited_title":"In: International Workshop on Coding and Cryptography","cited_arxiv_id":null,"evidence_quote":"Welch–Berlekamp-like decoding for Gabidulin codes is what makes the recovered equivalent trapdoor decrypt ciphertexts."},{"cited_title":"Journal of cryptology21(2), 280–301 (2008)","cited_arxiv_id":null,"evidence_quote":"Overbeck's Frobenius-sum distinguisher is the structural baseline the attack extends to recover the punctured Gabidulin code."},{"cited_title":"In: Advances in Cryptology - EUROCRYPT 2026 (2026), https://eprint.iacr.org/2025/1292, to appear","cited_arxiv_id":null,"evidence_quote":"The previous MinRank kernel key-recovery attack that broke 5 of 16 parameter sets, the baseline the new attack must beat."},{"cited_title":"Percentage","cited_arxiv_id":null,"evidence_quote":"Supports the idea that a short punctured code can be extended while preserving the MDS property, though Gabidulin structure allows extension to full length n."}],"review_version":1}