{"id":"955930fa-be49-4218-925e-4215f26b80f7","arxiv_id":"2605.27535","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves that every non-MDS matrix admits related differentials, every odd-order symmetric MDS matrix admits them, most circulant matrices admit them, and gives an explicit 15-constraint criterion for 3x3 MDS matrices over finite fields.","lead":"The paper proves mathematical conditions under which linear diffusion matrices in block ciphers must exhibit related-differential structures exploitable in attacks. Designers of AES-like ciphers can use these results to rule out broad families of matrices that would otherwise appear safe under the MDS criterion alone.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader correctly flags that the claims are proof-dependent and that the definition of related differentials is the transfer point from prior work. No additional load-bearing gap (e.g., field characteristic exceptions, overlooked matrix classes, or non-transferable attack model) appears in the stated results.","tokens_in":1816,"tokens_out":275,"duration_ms":15373,"concrete_test":"Independently re-derive the 15 polynomial constraints for 3×3 MDS matrices (final section) from the definition of related differentials without using computer algebra; confirm they are necessary and sufficient by testing on a small field such as F_{2^4} with all 3×3 MDS matrices.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The four theorems are presented as algebraic results derived from the matrix properties over finite fields and the definition of related differentials. The necessity claims (non-MDS always admit them; odd-order symmetric MDS always admit them; circulant case except n ≡ ±2 mod 12) follow from explicit constructions or exhaustive case analysis in the respective sections. The 3×3 criterion is stated as 15 explicit polynomial equations, which is a concrete, checkable output. No internal contradiction or hidden assumption beyond the cited definition of related differentials is visible.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proves four main results on related differentials in linear layers: (1) every non-MDS matrix admits a nontrivial pair of related differentials, establishing necessity of the MDS property; (2) every odd-order symmetric MDS matrix admits related differentials; (3) related differentials are unavoidable for every circulant matrix of order n with n ≢ ±2 (mod 12); and (4) an explicit necessary-and-sufficient criterion consisting of 15 polynomial constraints characterizes 3×3 MDS matrices over F_{2^m} that avoid related differentials.","tokens_in":1888,"tokens_out":362,"duration_ms":32152,"significance":"If the algebraic derivations hold, the results provide a rigorous classification of when the MDS property is necessary but not always sufficient to avoid related-differential structure, with explicit constructions for the symmetric and circulant cases and a concrete, checkable polynomial criterion for the 3×3 case. These strengthen resistance arguments in AES-like designs beyond the classical branch-number analysis and supply falsifiable algebraic tests that can be verified directly over finite fields.","major_comments":[],"minor_comments":[{"comment":"The abstract and introduction should explicitly reference the precise definition of 'related differential' from Bardeh-Rijmen 2022 (or the cited prior work) to ensure the necessity claims transfer unambiguously to the attack model used here.","section":"Abstract"},{"comment":"In the circulant-matrix theorem, the proof sketch for the n ≢ ±2 (mod 12) case would benefit from a short table or enumerated case breakdown showing how the exhaustive analysis covers the residue classes.","section":"Circulant case section"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive assessment of our work and the recommendation for minor revision. No specific major comments were raised in the report, so we have no points requiring point-by-point rebuttal at this stage. We remain available to incorporate any minor clarifications or corrections identified during the editorial process.","responses":[],"tokens_in":1282,"tokens_out":79,"duration_ms":12264,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's core contribution is four explicit theorems that classify when related differentials must appear in linear layers. Non-MDS matrices always admit them, odd-order symmetric MDS matrices always do, circulant matrices do except when order n satisfies n ≡ ±2 mod 12, and 3×3 MDS matrices over F_{2^m} avoid them exactly when 15 specific polynomial constraints hold. These are stated as necessity and sufficiency claims derived from the matrix definitions and the related-differential notion in the cited prior work.\n\nThe results organize matrix families that the MDS branch-number criterion alone left open and supply checkable algebraic conditions instead of existence arguments. The circulant strengthening and the odd-order symmetric case appear to be new relative to the references. The 15-constraint criterion for the 3×3 case is a concrete output that designers could in principle verify directly.\n\nThe main soft spot is that the abstract and summary give the statements cleanly but the full case analysis and polynomial derivations are not reproduced here, so any gaps in the exhaustive checks for small orders or field characteristics would only surface on reading the proofs. The mod-12 exception for circulants is noted without further examples or discussion of whether those orders are practically relevant, which is a minor omission rather than a flaw. No circularity or post-hoc fitting is visible in the claims.\n\nThis is for cryptographers working on diffusion-layer design in AES-like ciphers who need tighter constraints than the classical MDS property. A reader already familiar with the Daemen-Rijmen and Bardeh-Rijmen definitions will get usable obstructions. The work shows clear algebraic engagement with the literature and deserves a serious referee to check the derivations in detail.\n\nRecommendation: send to peer review.","headline":"Four algebraic necessity results on related differentials give concrete obstructions for MDS matrix classes that were previously treated as interchangeable.","tokens_in":2392,"tokens_out":416,"would_cite":false,"duration_ms":17239,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Every non-MDS matrix admits related differentials, as do all odd-order symmetric MDS matrices and most circulant matrices.","keywords":["related differentials","MDS matrices","linear layers","differential cryptanalysis","AES-like ciphers","circulant matrices","symmetric matrices","finite fields"],"falsifier":"A single non-MDS matrix with no nontrivial related-differential pair, or a single odd-order symmetric MDS matrix with none, would disprove the necessity claims.","tokens_in":2698,"feed_emoji":"","tokens_out":720,"duration_ms":37882,"temperature":0.7,"pith_summary":"The paper proves that the MDS property is necessary but not sufficient to prevent related differentials in linear layers of AES-like ciphers. Any matrix that is not MDS has a nontrivial related-differential pair. Symmetric MDS matrices of odd order always exhibit them, which eliminates many Cauchy constructions. Circulant matrices of order n also always have them unless n is congruent to plus or minus 2 modulo 12. For the special case of 3 by 3 MDS matrices over fields of characteristic 2, absence of related differentials is equivalent to satisfying a fixed list of 15 polynomial constraints.","feed_headline":"Related differentials unavoidable in non-MDS and many MDS linear layers","feed_subtitle":"Every non-MDS matrix has them; so do all odd-order symmetric MDS matrices and circulants except when order ≡ ±2 mod 12; 15 constraints decid","key_machinery":"Related differentials, pairs of input-output differences linked by the linear layer that enable chained differential trails beyond what branch number alone controls.","core_discovery":"The central claim is that related differentials are unavoidable outside narrow algebraic conditions: every non-MDS matrix admits a nontrivial pair, every odd-order symmetric MDS matrix admits them, and every circulant matrix of order n with n not congruent to plus or minus 2 modulo 12 admits them. For 3 by 3 MDS matrices over F_{2^m}, the absence of related differentials holds if and only if 15 explicit polynomial constraints are satisfied.","pith_inferences":["Existing ciphers that already use odd-order symmetric or non-conforming circulant layers may carry previously unrecognized attack surfaces.","The results invite similar classification for other common matrix families such as Hadamard or Toeplitz forms.","A natural next step is to lift the 15-constraint test to 4 by 4 or larger MDS matrices over the same fields.","Lightweight ciphers that replace matrix diffusion with bit-permutation or other non-matrix layers may require an analogous analysis."],"forward_implications":["Any cipher whose linear layer is not MDS is immediately open to related-differential exploitation.","Symmetric MDS matrices of odd order are ruled out for designs that must avoid related differentials.","Circulant layers are restricted to orders satisfying the stated congruence to have any chance of avoiding the structure.","The 15-constraint criterion gives a concrete, checkable test for all 3 by 3 MDS matrices over characteristic-2 fields.","Cipher designers must now verify their chosen matrix against these classes rather than relying on the MDS property alone."],"fun_headline_variants":["Non-MDS matrices always admit related differentials","Odd-order symmetric MDS matrices admit related differentials","Circulants admit related differentials unless n ≡ ±2 mod 12","15 constraints decide related differentials in 3x3 MDS matrices","Related differentials unavoidable except narrow algebraic cases"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The definition and attack model for related differentials match exactly those introduced in the cited prior references.","fun_headline_variants_meta":{"raw":{"variants":["Non-MDS matrices always admit related differentials","Odd-order symmetric MDS matrices admit related differentials","Circulants admit related differentials unless n ≡ ±2 mod 12","15 constraints decide related differentials in 3x3 MDS matrices","Related differentials unavoidable except narrow algebraic cases"]},"model":"grok-4.3","cost_usd":0.002725,"raw_usage":{"total_tokens":1471,"prompt_tokens":708,"num_sources_used":0,"completion_tokens":72,"cost_in_usd_ticks":27253000,"prompt_tokens_details":{"text_tokens":708,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":691,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":708,"tokens_out":72,"duration_ms":6263,"temperature":1.0,"reasoning_tokens":691,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T17:02:24.614023+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A single non-MDS matrix with no nontrivial related-differential pair, or a single odd-order symmetric MDS matrix with none, would disprove the necessity claims.","supporting_citations":[],"review_version":1}