Paper 2026/1251

Related Differentials of $4\times4$ MDS Matrices: A Complete Characterization

Abstract

A pair of differences $(x,y)$ is a \emph{related differential} for a linear layer $M$ if, for every coordinate at both the input and the output, at least one of the two values vanishes or the two values coincide. Related differentials underlie the zero-difference attack on AES of Bardeh and Rijmen, and the question of which maximum distance separable (MDS) matrices admit them was raised by Daemen and Rijmen, who showed that every $4\times4$ circulant MDS matrix does while some Hadamard ones do not. In earlier work the $3\times3$ MDS matrices over $\mathbb{F}_{2^r}$ admitting related differentials were characterized by fifteen explicit equations. In this paper we settle the $4\times4$ case completely: an MDS matrix $M=DNE$ over $\mathbb{F}_{2^r}$ admits a related differential if and only if at least one of $280$ explicit polynomial equations in the nine free entries of its reduced form $N$ holds. The equations, $70$ quadratic and $210$ cubic, are pairwise distinct, irreducible and pairwise coprime, and fall into $27$ orbits under the natural symmetries. We further determine the structure of the equation set: the fifteen equations of the $3\times3$ case are exactly the points of $\mathrm{PG}(3,2)$, while the $280$ equations span a $14$-dimensional $\mathbb{F}_2$-space, satisfy exactly $560$ additive relations, and contain exactly $840$ pairs that can never hold simultaneously on an MDS matrix. The discarded zero patterns split into $525$ whose determinant condition is equivalent to the failure of MDS-ness and $289$ vacuous cases. Over $\mathbb{F}_8$, the smallest field carrying $4\times4$ MDS matrices, exhaustive enumeration shows that there are exactly $720$ reduced MDS matrices; each satisfying exactly $28$ of the equations and each equation being satisfied by exactly $72$ matrices; in particular every $4\times4$ MDS matrix over $\mathbb{F}_8$ admits a related differential. Over $\mathbb{F}_{2^{10}}$ we exhibit an explicit MDS matrix admitting none. All results are verified by exact computation against an independent exhaustive search.