Analyzing Linear Layers in Related-Differential Cryptanalysis

arXiv:2605.27535 · cs.CR · Submitted 2026-05-26 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "Analyzing Linear Layers in Related-Differential Cryptanalysis".

Elias: Here's the gist of the paper. In this work, researchers systematically investigate the conditions under which linear layers in AES-like ciphers avoid or exhibit related differentials, identifying matrix classes for which such structure is unavoidable <ref:2605.27535#pg2>.

Nadia: Necessity of MDS Property The paper proves that every non-MDS matrix admits a nontrivial pair of related differentials, establishing that the MDS property is necessary for avoiding these differentials <ref:2605.27535#pg4>.

Elias: This finding narrows the search space for resistant linear layers to the MDS setting <ref:2605.27535#pg5>.

Nadia: Vulnerability of Symmetric Matrices The investigation shows that all odd-order symmetric MDS matrices necessarily possess related differentials, indicating that symmetry in odd dimension constitutes an inherent vulnerability from the viewpoint of related-differential cryptanalysis <ref:2605.27535#pg9>.

Title and authors: Nadia: So let's start by looking at what this paper actually is called and who wrote it. It's titled "Analyzing Linear Layers in Related-Differential Cryptanalysis".

Elias: The authors are Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta >

Priya: I always look at the authors to see what their background is; this team seems to have a mix of cryptographic and measurement expertise here >

Nadia: Right. Yogesh and Akshay seem to be focused on the construction side, looking at how these matrices are built recursively or algebraically >

Elias: And Susanta brings in that perspective on what the data actually shows, which is crucial when we're talking about security claims >

Priya: So we need to see how they balance the theoretical construction proofs with the practical implications for actual cipher design and analysis >

The paper's summary: Nadia: The paper summarizes that diffusion layers in AES-like ciphers usually use MDS matrices because they give optimal branch numbers, which means strong diffusion guarantees against differential and linear cryptanalysis >

Elias: But the authors point out that even with an MDS matrix, related-differential structure can still appear beyond what the basic MDS criterion catches, as shown by previous work like Daemen and Rijmen in two thousand nine > <ref:2605.27535#pg1>

Priya: That’s a key distinction. It's not just about whether it's MDS or not; there are these deeper properties we have to worry about >

Nadia: And then they build on that, showing that for any non-MDS matrix, it always has at least one pair of related differentials, which proves the MDS property is necessary for avoiding them >

Elias: That necessity is what allows them to focus their search space down specifically to the MDS setting when looking for resistant layers >

Priya: So they are essentially saying that if you want a secure layer, you first have to satisfy this strong diffusion requirement, and then check for these deeper structural vulnerabilities >

Nadia: They go further by showing that odd-order symmetric MDS matrices automatically admit related differentials, which is a vulnerability inherent to odd dimensions in this context >

Elias: That result specifically rules out broad families of constructions that rely on symmetry, like some Cauchy-based designs >

The paper's improvements: Nadia: Now let's talk about what the authors themselves suggest we do next, because they point out some avenues for improvement in the research direction >

Elias: They highlight that their current characterization of when three by three MDS matrices have related differentials is complete, but they need to push that analysis up to four by four matrices >

Priya: That extension would be important because it tests if the pattern seen in the small case holds true for larger dimensions as well >

Nadia: And there’s a specific focus on constructing lightweight MDS matrices that avoid these related differentials, which is something they see as a key practical challenge >

Elias: They are pointing toward using their new algebraic conditions to automatically test candidate matrices against those fifteen rules to find ways around them >

Priya: That idea of using the algebraic conditions to filter out bad candidates before they get built is what I find most useful for practical implementation research >

Conclusion: Nadia: So wrapping up, the paper shows that while being MDS is necessary to avoid related differentials, it’s not enough by itself because of those other structural issues >

Elias: They confirm that the findings necessitate focusing on the MDS setting but also checking for symmetry and other specific matrix families like circulant ones >

Priya: From my view, the real contribution is giving us a concrete roadmap: first, check if it's MDS, then check for odd symmetry or circulant properties depending on your dimension >

Nadia: And that’s how they wrap up their analysis of "Analyzing Linear Layers in Related-Differential Cryptanalysis" >

Elias: It sets the stage for future research into extending these three by three characterizations to larger matrices and developing new matrix families that are resistant to these specific types of cryptanalytic attacks >

Priya: It gives us a clear understanding of what security means in this context, telling us exactly which matrix constructions we need to avoid or scrutinize first before we trust them for any cipher design >

Scientific Analysis Group, DRDO · Department of Electrical and Computer Engineering, University of Waterloo

cs.CR

Submitted: 2026-05-26

Updated: 2026-11-10

Journal ref: IEEE Transactions on Information Theory, 2026

DOI: 10.1109/TIT.2026.3752341

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 69/100

The gist: In this work, researchers systematically investigate the conditions under which linear layers in AES-like ciphers avoid or exhibit related differentials…

Key concepts

Related Differentials
These are specific patterns of differences in the cipher's output that occur when the input differences follow a certain linear relationship. Finding these patterns is crucial because they can be exploited by cryptanalysts to break ciphers.
MDS Property
A Maximum Distance Separable (MDS) matrix is a linear transformation that maximizes the diffusion of input changes. It ensures that any small change in the input spreads widely across all parts of the output, which is vital for strong security against cryptanalysis.
Symmetric Matrix Vulnerability
The paper shows that symmetric MDS matrices with odd dimensions inherently possess related differentials. This means symmetry in odd-sized layers creates an unavoidable weakness exploitable by related-differential attacks, ruling out some constructions.

Terminology

Summary

In this work, researchers systematically investigate the conditions under which linear layers in AES-like ciphers avoid or exhibit related differentials, identifying matrix classes for which such structure is unavoidable <ref:2605. p. 0

Where the paper says it

However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES. In this work, we systematically investigate the conditions under which linear layers avoid or exhibit these differentials, identifying matrix classes for which such structure is unavoidable.

27535#pg2>.

Necessity of MDS Property

The paper proves that every non-MDS matrix admits a nontrivial pair of related differentials, establishing that the MDS property is necessary for avoiding these differentials <ref:2605.27535#pg4>. This finding narrows the search space for resistant linear layers to the MDS setting <ref:2605. p. 2

Where the paper says it

We answer this question affirmatively by proving that the MDS property is necessary for avoiding related differentials: every non-MDS matrix admits related differentials. Therefore, the search for linear layers resistant to related-differential cryptanalysis must be confined to the MDS setting.

27535#pg5>.

Vulnerability of Symmetric Matrices

The investigation shows that all odd-order symmetric MDS matrices necessarily possess related differentials, indicating that symmetry in odd dimension constitutes an inherent vulnerability from the viewpoint of related-differential cryptanalysis <ref:2605.27535#pg9>. This result rules out broad families of Cauchy-based constructions <ref:2605. p. 0

Where the paper says it

We first prove that every non-MDS matrix admits a nontrivial pair of related differentials, showing that the MDS property is necessary for avoiding them. We then establish that every odd-order symmetric MDS matrix admits related differentials, which rules out broad families of Cauchy-based constructions.

27535#pg10>.

Vulnerability of Circulant Matrices

The study establishes that circulant MDS matrices of order n admit related differentials whenever n is not congruent to ±2 modulo 12, providing a general characterization for this matrix family. This result is based on the modular conditions derived from polynomial decomposition. p. 9

Where the paper says it

However, this same structural regularity creates systematic vulnerabilities to related-differential attacks. This section provides a broad characterization of when circulant MDS matrices possess related differentials, developing three fundamental lemmas based on modular conditions on the matrix dimension and culminating in a unified theorem (Theorem 5) that identifies a broad class of vulnerable orders.

Complete Characterization for 3 × 3 Matrices

A complete algebraic characterization of when 3 × 3 MDS matrices possess related differentials is derived through a systematic case-by-case analysis of all possible weight patterns for related triplets. This characterization involves deriving fifteen algebraic conditions that completely determine the related-differentials property. p. 9

Where the paper says it

This section provides a broad characterization of when circulant MDS matrices possess related differentials, developing three fundamental lemmas based on modular conditions on the matrix dimension and culminating in a unified theorem (Theorem 5) that identifies a broad class of vulnerable orders. A circulant matrix M of order n × n over F2m is completely determined by its first row vector [x1, x2, .

The paper concludes by enumerating the number of 3 × 3 MDS matrices that have no pair of related differentials over various finite fields. p. 3
Where the paper says it

MATHEMATICAL PRELIMINARIES In this section, we collect the notation and basic definitions used throughout the paper. We work over finite fields of characteristic 2 and recall the notions of branch number, MDS matrices, and related differentials that will be used in the subsequent sections.

Conclusion and Future Directions

The results demonstrate that the MDS property is necessary but not sufficient to avoid related differentials, as shown by Corollaries 2 and 3. The findings suggest future research should focus on extending the characterization obtained for the 3 × 3 case to 4 × 4 matrices and constructing lightweight MDS matrices without related differentials. p. 0

Where the paper says it

We also substantially strengthen the circulant case by proving that related differentials are unavoidable for every circulant matrix of order n with n ̸≡ ±2 (mod 12). Finally, we revisit the characterization of 3 × 3 MDS matrices over F2m for the absence of related differentials, and derive an explicit necessary and sufficient criterion in terms of 15 polynomial constraints.

The analysis also points toward a natural conjecture regarding the remaining unresolved cases in the circulant setting. p. 2
Where the paper says it

Therefore, the search for linear layers resistant to related-differential cryptanalysis must be confined to the MDS setting. • Vulnerability of symmetric matrices: Since many cryptographically relevant matrix classes, including Hadamardtype constructions, are symmetric, it is natural to ask whether symmetry itself influences the existence of related differentials.

TABLE I

ENUMERATION OF 3 × 3 MDS MATRICES AND THEIR SUBCLASS THAT ADMIT NO RELATED DIFFERENTIAL (RD) PAIR OVER FINITE FIELDS.

Finite Field F23 7 MDS 5 × 390 0

F24 155 × 24206 155 × 4464

F25 315 × 658590 315 × 361440

F26 635 × 13392062 635 × 10298160

F27 1275 × 240234750 1275 × 212254560

F28 2555 × 4064764286 2555 × 3827268144

REFERENCES

[1] J. Daemen and V. p. 0

Where the paper says it

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES.

p. 0
Where the paper says it

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES.

Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, ser. p. 0
Where the paper says it

INTRODUCTION SPN-based block ciphers represent the dominant paradigm in modern symmetric cryptography, exemplified by the Advanced Encryption Standard (AES) [1]. At the core of SPN design lies the wide-trail strategy [2], which combines nonlinear substitution layers with a linear diffusion layer to achieve strong resistance against differential and linear cryptanalysis.

Information Security and Cryptography. p. 0
Where the paper says it

Index Terms Diffusion layer, MDS matrix, circulant matrix, related differentials I. INTRODUCTION SPN-based block ciphers represent the dominant paradigm in modern symmetric cryptography, exemplified by the Advanced Encryption Standard (AES) [1].

Springer, 2002

[2] J. Daemen, Cipher and hash function design, strategies based on linear and differential cryptanalysis, PhD Thesis. p. 0

Where the paper says it

INTRODUCTION SPN-based block ciphers represent the dominant paradigm in modern symmetric cryptography, exemplified by the Advanced Encryption Standard (AES) [1]. At the core of SPN design lies the wide-trail strategy [2], which combines nonlinear substitution layers with a linear diffusion layer to achieve strong resistance against differential and linear cryptanalysis.

K.U.Leuven, 1995

[3] V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers, and E. De Win, “The cipher SHARK,” in Fast Software Encryption

[4] J. Daemen, L. Knudsen, and V. Rijmen, “The block cipher Square,” in Fast Software Encryption

[5] J. Lacan and J. Fimes, “A Construction of Matrices with No Singular Square Submatrices,” in Finite Fields and Applications

[6] K. C. Gupta and I. G. Ray, “On constructions of involutory MDS matrices,” in International Conference on Cryptology in Africa

[7] K. C. Gupta, S. K. Pandey, I. G. Ray, and S. Samanta, “Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results,” Advances in Mathematics of Communications

[8] K. C. Gupta, S. K. Pandey, and S. Samanta, “On the Direct Construction of MDS and Near-MDS Matrices,” Advances in Mathematics of Communications

[9] M. Sajadieh, M. Dakhilalian, H. Mala, and B. Omoomi, “On construction of Involutory MDS Matrices from Vandermonde Matrices in GF(2q),” Designs, Codes and Cryptography

[10] D. Augot and M. Finiasz, “Direct Construction of Recursive MDS Diffusion Layers Using Shortened BCH Codes,” in Fast Software Encryption – FSE 2014

[11] K. C. Gupta, S. K. Pandey, and A. Venkateswarlu, “Towards a general construction of recursive MDS diffusion layers,” Designs, Codes and Cryptography

[12] ——, “On the direct construction of recursive MDS matrices,” Designs, Codes and Cryptography

[13] A. Kesarwani, S. Sarkar, and A. Venkateswarlu, “Exhaustive Search for Various Types of MDS Matrices,” IACR Transactions on Symmetric Cryptology

[14] S. M. Sim, K. Khoo, F. Oggier, and T. Peyrin, “Lightweight MDS Involution Matrices,” in Fast Software Encryption – FSE 2015

[15] M. Liu and S. M. Sim, “Lightweight MDS Generalized Circulant Matrices,” in Fast Software Encryption – FSE 2016

[16] Y. Li and M. Wang, “On the construction of lightweight circulant involutory mds matrices,” in Fast Software Encryption – FSE 2016

[17] G. G. Guzel, M. T. Sakalli, S. Akleylek, V. Rijmen, and Y. p. 0

Where the paper says it

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES.

C¸ engellenmis¸, “A new matrix form to generate all 3 × 3 involutory MDS matrices over F2m,” Information Processing Letters

[18] M. K. Pehlivanoglu, M. T. Sakalli, S. Akleylek, N. Duru, and V. Rijmen, “Generalisation of Hadamard matrix to generate involutory MDS ˜ matrices for lightweight cryptography,” IET Information Security

[19] Y. Kumar, P. R. Mishra, S. Samanta, K. p. 0

Where the paper says it

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES.

C. Gupta, and A. Gaur, “Construction of all MDS and involutory MDS matrices,” Advances in Mathematics of Communications

[20] Y. Kumar, P. R. Mishra, S. Samanta, and A. p. 0

Where the paper says it

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES.

Gaur, “A systematic construction approach for all 4 × 4 involutory MDS matrices,” Journal of Applied Mathematics and Computing

[21] J. Daemen and V. Rijmen, “New criteria for linear maps in AES-like ciphers,” Cryptography and Communications

[22] N. Ghaedi Bardeh and V. p. 0

Where the paper says it

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES.

Rijmen, “New key-recovery attack on reduced-round aes,” IACR Transactions on Symmetric Cryptology

[23] S. Rønjom, N. G. Bardeh, and T. p. 0

Where the paper says it

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES.

Helleseth, “Yoyo Tricks with AES,” in Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security

[24] S. Jha, S. Li, and D. Gligoroski, “Construction of hadamard-based mixcolumns matrices resistant to related-differential cryptanalysis,” IACR Communications in Cryptology

[25] K. Otal, A. M. Sulc¸e, and O. Yayla, “On the Cryptographic Resilience of MDS Matrices,” ¨ Cryptology ePrint Archive

[26] M. R. Albrecht, B. Driessen, E. B. Kavun, G. Leander, C. Paar, and T. Yalc¸ın, “Block Ciphers – Focus on the Linear Layer (feat. p. 1

Where the paper says it

While the above approaches primarily focus on achieving the MDS property and reducing implementation cost, it has also been observed that additional structural properties of the diffusion layer can influence cryptographic security. In particular, Daemen and Rijmen [21] investigated linear transformations used in AES-like block ciphers in order to understand which properties of the linear layer influence the behavior of differentials and characteristics over super S-boxes.

PRIDE),” in Advances in Cryptology – CRYPTO 2014

[27] S. Banik, A. Bogdanov, T. Isobe, K. Shibutani, H. Hiwatari, T. Akishita, and F. Regazzoni, “Midori: A Block Cipher for Low Energy,” in Advances in Cryptology – ASIACRYPT 2015

[28] C. Beierle, J. Jean, S. Kolbl, G. Leander, A. Moradi, T. Peyrin, Y. Sasaki, P. Sasdrich, and S. M Sim, “The SKINNY Family of Block ¨ Ciphers and Its Low-Latency Variant MANTIS,” in Advances in Cryptology – CRYPTO 2016

[29] B. Bilgin, A. Bogdanov, M. Knezevi ˇ c, F. Mendel, and Q. Wang, “Fides: Lightweight Authenticated cipher with Side-Channel Resistance ´ for Constrained Hardware,” in Cryptographic Hardware and Embedded Systems - CHES 2013

[30] J. Borghoff, A. Canteaut, T. Guneysu, E. B. Kavun, M. Knezevic, L. R. Knudsen, G. Leander, V. Nikov, C Paar, C Rechberger, P Rombouts S S Thomsen and T Yalc¸ın “PRINCE – A Low-Latency Block Cipher for Pervasive Computing Applications,” in Advances in Cryptology – ASIACRYPT 2012

[31] F. MacWilliams and N. Sloane, The Theory of Error Correcting Codes. p. 3

Where the paper says it

MDS matrix finds its practical applications as a diffusion layer in cryptographic primitives. The concept of the MDS matrix comes from coding theory, specifically from the realm of maximum distance separable (MDS) codes.

North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977

--- Page 1 ---

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis <ref:2605.27535#pg2>. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES <ref:2605. p. 0

Where the paper says it

Analyzing Linear Layers in Related-Differential Cryptanalysis Yogesh Kumar, Akshay Ankush Yadav, and Susanta Samanta Abstract In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES.

27535#pg2>.

--- Page 3 ---

Motivated by the importance of MDS matrices in diffusion layer design, their construction has been studied extensively in the literature. Existing approaches can be classified broadly into two categories: non-recursive and recursive. p. 1

Where the paper says it

Motivated by the importance of MDS matrices in diffusion layer design, their construction has been studied extensively in the literature. Existing approaches can be classified broadly into two categories: non-recursive and recursive.

Both categories can be further divided into algebraic, search-based, and hybrid methods. p. 1
Where the paper says it

In recursive constructions, one typically begins with a sparse matrix A of order n, with entries chosen so that An is MDS. Both categories can be further divided into algebraic, search-based, and hybrid methods.

--- Page 5 ---

The security of SPN block ciphers against differential and linear cryptanalysis depends critically on the branch number [2] of the linear diffusion layer <ref:2605.27535#pg2>. A linear transformation M is called Maximum Distance Separable (MDS) if its branch number attains the theoretical maximum, namely Bd(M) = Bl(M) = n + 1 <ref:2605. p. 3

Where the paper says it

For a linear transformation M : F n 2m → F n 2m, the differential branch number is defined as Bd(M) = min x̸=0 wt(x) + wt(Mx) , and the linear branch number is defined as Bl(M) = min x̸=0 wt(x) + wt(MT x) . A linear transformation M is called Maximum Distance Separable (MDS) if its branch number attains the theoretical maximum, namely Bd(M) = Bl(M) = n + 1.

27535#pg2>.

--- Page 7 ---

Theorem 2. Let M = [aij]n×n be a matrix of order n. p. 4

Where the paper says it

We first begin by showing that any non-MDS matrix contains related differentials. Let M = [aij ]n×n be a square matrix of order n.

If M is not an MDS matrix, then M has at least one nontrivial pair of related differentials <ref:2605. p. 4
Where the paper says it

Let M = [ai,j ]n×n be a matrix of order n. If M is not an MDS matrix, then M has at least one nontrivial pair of related differentials.

27535#pg2>.

--- Page 8 ---

Theorem 3. Let M be an invertible square matrix of order n. p. 6

Where the paper says it

In the following theorem, we show that the property of not having related differentials is also preserved under the inverse operation. Let M be an invertible square matrix of order n.

Then, M does not have any related differential pair if and only if M−1 does not have any related differential pair <ref:2605. p. 3
Where the paper says it

The pair (u, v) is called a differential of the linear map M. We restate the definitions of related differences and related differentials from [21].

27535#pg2>.

--- Page 9 ---

Theorem 4. Let M be a symmetric MDS matrix of order n. p. 7

Where the paper says it

It is important to note that the MDS property is not sufficient to avoid related differentials, as we will demonstrate in the subsequent results. Let M be a symmetric MDS matrix of order n.

If n is odd, then M admits a related differential pair <ref:2605. p. 7
Where the paper says it

Let M be a symmetric MDS matrix of order n. If n is odd, then M admits a related differential pair.

27535#pg2>.

--- Page 10 ---

Corollary 2. Every Type 2 Cauchy-based MDS matrix of odd order admits a related differential pair <ref:2605. p. 9

Where the paper says it

Corollary 2. Every Type 2 Cauchy-based MDS matrix of odd order admits a related differential pair.

27535#pg2>.

--- Page 12 ---

Corollary 3. Every left-circulant MDS matrix of odd order admits a related differential pair <ref:2605. p. 9

Where the paper says it

Every Type 2 Cauchy-based MDS matrix of odd order admits a related differential pair. In [15], the authors suggest a new category of matrices known as left-circulant matrices.

27535#pg2>.

--- Page 13 ---

Lemma 4. If (u, v) and (u′, v′) are related differentials over a linear map with an associated n × n matrix that is MDS, then min wt(u) + wt(v), wt(u′) + wt(v′), wt(t) + weight of the triplet ≤ n + jn/3k <ref:2605. p. 4

Where the paper says it

Two differentials (u, Mu) and (v, Mv) for a linear map are called related differentials if and only if (u, v) and (Mu, Mv) are related differences. Consider the matrix M =         0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0         over the finite field F2m.

27535#pg2>.

--- Page 14 ---

Lemma 5. If (u, v, t) are related differences triplet in F2m with t = u ⊕ v, then wt(u) + wt(v) + wt(t) ≤ 2n <ref:2605. p. 4

Where the paper says it

Two differentials (u, Mu) and (v, Mv) for a linear map are called related differentials if and only if (u, v) and (Mu, Mv) are related differences. Consider the matrix M =         0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0         over the finite field F2m.

27535#pg2>.

--- Page 15 ---

Lemma 6. Let aiy + biz = ci, i ∈ 3 be a system of linear equations in two variables over F2m. p. 6

Where the paper says it

Thus we have the following system of (n − r) homogeneous equations: X 1≤j≤n,j∈Jc ai,jxj + Xr t=1 aijt st ! The above system has n − r + 1 variables, namely xj and α.

Then this system has a consistent solution if and only if a1 b1 c1 a2 b2 c2 a3 b3 c3 = 0 <ref:2605. p. 6
Where the paper says it

The above system has n − r + 1 variables, namely xj and α. Thus, this system of equations will definitely have a nontrivial solution.

27535#pg2>.

--- Page 17 ---

Lemma 7. For any nonsingular diagonal matrices D1 and D2, the matrix M has a related differential pair if and only if the representative matrix M1 given in (4) has a related differential pair

--- Page 20 ---

Theorem 6. Let M = (mij) be a n × n matrix over F2m. p. 4

Where the paper says it

Consider the matrix M =         0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0         over the finite field F2m. Let u = [1, 0, 0, 0], v = [0, 0, 1, 0].

Then, there exist unique n × n matrices D1, D2, and M1 over F2m such that M = D1M1D2

--- Page 20 ---

Lemma 7.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Systematic verification of related differential properties for 3x3 MDS matrices can be achieved by implementing Algorithm 1, which uses a set of fifteen algebraic conditions derived from Theorem 7 to determine if a matrix avoids related differentials. This allows for efficient checking against the complete characterization provided in the paper.

  2. The AI system can be enhanced to automatically generate and test candidate matrices against the fifteen conditions Ci(a, b, c, d) = 0 listed in Theorem 7 to verify resistance to related differential cryptanalysis. This capability is essential for constructing new light-weight MDS matrices without related differentials.

  3. The system can be programmed to recognize structural properties of circulant and symmetric matrices that inherently guarantee the existence of related differentials based on the paper's proofs (Lemma 1, Lemma 2, and Corollary 3). This enables the AI to quickly filter out entire classes of matrix constructions that are known vulnerabilities.

  4. The system can be designed to implement a search strategy specifically targeting matrices where n is not congruent to plus or minus two modulo twelve for circulant matrices. This ensures that the construction process focuses only on matrix orders known to potentially avoid related differentials, as stated in Theorem 5.

Abstract

In AES-like ciphers, diffusion layers are commonly instantiated using MDS matrices, since their optimal branch number yields strong diffusion guarantees and underpins classical resistance arguments against differential and linear cryptanalysis. However, Daemen and Rijmen (2009) showed that linear layers may still exhibit related-differential structure beyond what the MDS criterion captures, and Bardeh and Rijmen (2022) demonstrated that this phenomenon can be exploited in attacks on reduced-round AES. In this work, we systematically investigate the conditions under which linear layers avoid or exhibit these differentials, identifying matrix classes for which such structure is unavoidable. We first prove that every non-MDS matrix admits a nontrivial pair of related differentials, showing that the MDS property is necessary for avoiding them. We then establish that every odd-order symmetric MDS matrix admits related differentials, which rules out broad families of Cauchy-based constructions. We also substantially strengthen the circulant case by proving that related differentials are unavoidable for every circulant matrix of order n with n plus or minus 2. Finally, we revisit the characterization of 3 times 3 MDS matrices over F 2 m for the absence of related differentials, and derive an explicit necessary and sufficient criterion in terms of 15 polynomial constraints.

Related papers