Matriz MDS

Una matriz MDS ( máxima distancia separable ) es una matriz que representa una función con ciertas propiedades de difusión que tienen aplicaciones útiles en criptografía . Técnicamente, una${\displaystyle m\times n}$matriz${\displaystyle A}$sobre un campo finito${\displaystyle K}$es una matriz MDS si es la matriz de transformación de una transformación lineal${\displaystyle f(x)=Ax}$de${\displaystyle K^{n}}$a${\displaystyle K^{m}}$de tal manera que no haya dos diferentes${\displaystyle (m+n)}$-tuplas de la forma${\displaystyle (x,f(x))}$coincidir en${\displaystyle n}$o más componentes. De forma equivalente, el conjunto de todos${\displaystyle (m+n)}$-tuplas${\displaystyle (x,f(x))}$es un código MDS , es decir, un código lineal que alcanza el límite Singleton .

Dejar${\displaystyle {\tilde {A}}={\begin{pmatrix}\mathrm {I} _{n}\\\hline \mathrm {A} \end{pmatrix}}}$sea ​​la matriz obtenida al unir la matriz identidad${\displaystyle \mathrm {I} _ {n}}$a${\displaystyle A}$. Entonces, una condición necesaria y suficiente para una matriz${\displaystyle A}$Ser SMD significa que cada posible${\displaystyle n\times n}$submatriz obtenida al eliminar${\displaystyle m}$filas de${\displaystyle {\tilde {A}}}$es no singular . Esto también es equivalente a lo siguiente: todos los subdeterminantes de la matriz${\displaystyle A}$son distintos de cero. Entonces una matriz binaria${\displaystyle A}$(es decir, sobre el campo con dos elementos) nunca es MDS a menos que tenga solo una fila o solo una columna con todos los componentes.${\displaystyle 1}$.

Los códigos Reed-Solomon poseen la propiedad MDS y se utilizan con frecuencia para obtener las matrices MDS empleadas en algoritmos criptográficos.

Serge Vaudenay sugirió usar matrices MDS en primitivas criptográficas para producir lo que él llamó multipermutaciones , funciones no necesariamente lineales con esta misma propiedad. ^{[ 1 ]} Estas funciones tienen lo que él llamó difusión perfecta : cambiando${\displaystyle t}$de los cambios de entrada al menos${\displaystyle m-t+1}$de las salidas. Mostró cómo explotar la difusión imperfecta para criptoanalizar funciones que no son multipermutaciones.

Las matrices MDS se utilizan para la difusión en cifrados de bloques como AES , SHARK , Square , Twofish , Anubis , KHAZAD , Manta , Hierocrypt , Kalyna , Camellia y HADESMiMC , y en el cifrado de flujo MUGI y la función hash criptográfica Whirlpool , Poseidon .

• Vicente Rijmen ; Joan Daemen ; Bart Preneel ; Antonio Bosselaers; Erik De Win (febrero de 1996). El tiburón cifrado (PDF/PostScript) . 3er Taller Internacional sobre Cifrado Rápido de Software (FSE '96). Cambridge : Springer-Verlag. págs . 99-111 . Consultado el 6 de marzo de 2007 . 
• Bruce Schneier ; John Kelsey ; Doug Whiting; David Wagner ; Chris Hall; Niels Ferguson (15 de junio de 1998). "El algoritmo de cifrado Twofish" (PDF/PostScript) . Consultado el 4 de marzo de 2007 .