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 m×n matrix A over a finite field K is an MDS matrix if it is the transformation matrix of a linear transformation f(x)=Ax from Kn to Km such that no two different (m+n)-tuples of the form (x,f(x)) coincide in n or more components. Equivalently, the set of all (m+n)-tuples (x,f(x)) is an MDS code, i.e. a linear code that reaches the Singleton bound.
Let Failed to parse (unknown function\begin): \tilde A = \left(\begin{array}{c}{\rm Id}_n\\ \hline{\rm A}\end{array}\right)
be the matrix obtained by joining the identity matrix Idn to A.
Then a necessary and sufficient condition for a matrix A to be MDS is that every possible n×n submatrix obtained by removing m rows from 
is non-singular.
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 t of the inputs changes at least m-t+1 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, Manta, Hierocrypt, and Camellia, and in the stream cipher MUGI and the cryptographic hash function WHIRLPOOL.
References
- Serge Vaudenay (November 16 1994). "On the Need
for Multipermutations: Cryptanalysis of MD4 and SAFER" (PDF/PostScript). 2nd International Workshop on
Fast Software Encryption (FSE '94): pp.286–297, Leuven:
Springer-Verlag . Retrieved on 2007-03-05. - Vincent Rijmen, Joan Daemen, Bart Preneel, Anton Bosselaers, Erik De Win (February 1996). "The Cipher SHARK" (PDF/PostScript). 3rd International Workshop on Fast Software Encryption (FSE '96): pp.99–111, Cambridge: Springer-Verlag. Retrieved on 2007-03-06.
- Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson (June 15 1998). "The Twofish Encryption Algorithm" (PDF/PostScript). Retrieved on 2007-03-04.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
