MDS matrix

An MDS matrix (Maximum Distance Separable) is a matrix representing a function with certain diffusion properties that have useful applications in cryptography. Technically, an formula_1 matrix formula_2 over a finite field formula_3 is an MDS matrix if it is the transformation matrix of a linear transformation formula_4 from formula_5 to formula_6 such that no two different formula_7-tuples of the form formula_8 coincide in formula_9 or more components.
Equivalently, the set of all formula_7-tuples formula_8 is an MDS code, i.e., a linear code that reaches the Singleton bound.
Let formula_12 be the matrix obtained by joining the identity matrix formula_13 to formula_2. Then a necessary and sufficient condition for a matrix formula_2 to be MDS is that every possible formula_16 submatrix obtained by removing formula_17 rows from formula_18 is non-singular. This is also equivalent to the following: all the sub-determinants of the matrix formula_2 are non-zero. Then a binary matrix formula_2 (namely over the field with two elements) is never MDS unless it has only one row or only one column with all components formula_21.
Reed–Solomon codes have the MDS property and are frequently used to obtain the MDS matrices used in cryptographic algorithms.
Serge Vaudenay suggested using MDS matrices in cryptographic primitives to produce what he called "multipermutations", not-necessarily linear functions with this same property. These functions have what he called "perfect diffusion": changing formula_22 of the inputs changes at least formula_23 of the outputs. He showed how to exploit imperfect diffusion to cryptanalyze functions that are not multipermutations.
MDS matrices are used for diffusion in such block ciphers as AES, SHARK, Square, Twofish, Anubis, KHAZAD, Manta, Hierocrypt, Kalyna and Camellia, and in the stream cipher MUGI and the cryptographic hash function Whirlpool.