Una matriz MDS ( maximum distance 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 matriz sobre un cuerpo finito es una matriz MDS si es la matriz de transformación de una transformación lineal de a tal que no hay dos -tuplas diferentes de la forma que coincidan en o más componentes. De manera equivalente, el conjunto de todas las -tuplas es un código MDS , es decir, un código lineal que alcanza el límite Singleton .
Sea la matriz obtenida al unir la matriz identidad con . Entonces, una condición necesaria y suficiente para que una matriz sea MDS es que cada submatriz posible obtenida al eliminar filas de no sea singular . Esto también es equivalente a lo siguiente: todos los subdeterminantes de la matriz son distintos de cero. Entonces, una matriz binaria (es decir, sobre el cuerpo con dos elementos) nunca es MDS a menos que tenga solo una fila o solo una columna con todos los componentes .
Los códigos Reed-Solomon tienen la propiedad MDS y se utilizan con frecuencia para obtener las matrices MDS utilizadas en algoritmos criptográficos.
Serge Vaudenay sugirió utilizar 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 : al cambiar las entradas, se modifican al menos 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 bloque 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.
