Paper 2025/2240

On the Cryptographic Resilience of MDS Matrices

Abstract

The zero-difference attack on AES, introduced by Bardeh and Rijmen in [ToSC 2022(2):43--62], exploits some structural properties -referred to as related differentials- in the AES MDS matrix. Daemen and Rijmen earlier demonstrated that these related differentials appear not only in the AES MixColumns matrix but in all $4\times 4$ circulant MDS matrices [CCDS 2009(1):47--69]. In the same paper, they also showed an example of $4\times 4$ Hadamard MDS matrices for which there exists no related differentials. Combining both results, we can say for example that some $4\times 4$ Hadamard MDS matrices are more ``secure" than any $4\times 4$ circulant MDS matrices. Recently, Jha et al. investigated whether it is possible to characterize $4\times 4$ Hadamard MDS matrices for which we can find no related differentials in [ IACR Commun. Cryptol. 2(1): 37 (2025)]. As a result, they gave a systematic method to construct such ``secure" matrices with respect to their parameters. In this paper, we investigate the same problem for all $2\times 2$ and $3\times 3$ matrices to understand the cryptographic resilience of MDS matrices both theoretically and practically. As a result, we obtain the following results: - There are no related differentials for any $2\times 2$ MDS matrices. - There exist related differentials for all $3\times 3$ circulant MDS matrices. - There exist related differentials for all $3\times 3$ involutory MDS matrices when the finite field has even size. - We characterize all $3\times 3$ MDS matrices for which there exist no related differentials when the size of the finite field is even. In this way, we fill a gap for the cryptographic resilience problem of MDS matrices over finite fields.