New Insights into Involutory and Orthogonal MDS Matrices

Resumen Técnico: Nuevas Perspectivas sobre Matrices MDS Involutorias y Ortogonales

Planteamiento del Problema
Las matrices de Distancia Máxima Separable (MDS) son fundamentales para las capas de difusión de los cifrados de bloque y funciones hash debido a sus números de rama óptimos. Aunque existe una literatura significativa sobre la construcción de candidatos MDS eficientes, ciertas propiedades estructurales —a saber, involutorias (autoinversas) y ortogonales (transpuesta-inversa)— son altamente deseables para reducir los costos de implementación al permitir circuitos idénticos o casi idénticos para el cifrado y el descifrado. Recientemente, estos conceptos se han generalizado en matrices "semi-involutorias" y "semi-ortogonales". Sin embargo, la investigación existente se ha centrado principalmente en proponer nuevas construcciones o en optimizar métricas de implementación. Existe una falta de comprensión sistemática respecto a las interconexiones estructurales entre estas variantes generalizadas (semi-involutorias/semi-ortogonales) y sus contrapartes convencionales (involutorias/ortogonales), particularmente en lo que respecta a su enumeración sobre cuerpos finitos $\mathbb{F}_{2^m}$.

Metodología
Los autores adoptan un enfoque de análisis estructural en lugar de proponer nuevas construcciones de matrices. La metodología central se basa en la descomposición única de matrices no singulares sobre $\mathbb{F}_{2^m}^*$ en la forma $M = D_1 M_1 D_2$, donde $D_1$ y $D_2$ son matrices diagonales no singulares y $M_1$ es una "matriz representativa" con una forma canónica específica (primera fila y columna compuestas por unos).

Pasos metodológicos clave incluyen:

1. Establecer Interconexiones: El artículo demuestra que las propiedades de ser involutoria, semi-involutoria, ortogonal o semi-ortogonal se preservan o transforman de maneras predecibles al aplicar la escala diagonal $D_1 M_1 D_2$.
2. Derivar Relaciones de Conteo: Al analizar las restricciones sobre $D_1$ y $D_2$ requeridas para que una matriz $M$ satisfaga propiedades específicas, los autores derivan relaciones bidireccionales entre los conteos de matrices generalizadas y sus contrapartes convencionales.
3. Caracterización Estructural: Los autores derivan la estructura algebraica general de las matrices ortogonales de orden $n$ arbitrario sobre $\mathbb{F}_{2^m}$ y especializan esto para $n=3$ y $n=4$.
4. Enumeración: Utilizando resultados de enumeración conocidos para matrices MDS involutorias y las relaciones estructurales derivadas, los autores calculan el número exacto de matrices MDS semi-involutorias y semi-ortogonales para órdenes y tamaños de campo específicos.

Contribuciones Clave y Resultados

• Interconexiones Estructurales: El artículo establece relaciones no triviales entre matrices semi-involutorias e involutorias, y entre matrices semi-ortogonales y ortogonales. Específicamente, se muestra que el número de matrices MDS involutorias de $n \times n$ es $(2^m - 1)^{n-1}$ veces el número de matrices MDS semi-involutorias de la forma $M_1$. Una correspondencia similar se demuestra para matrices semi-ortogonales y ortogonales.
• Enumeración de Matrices 3×3:
  • MDS Ortogonales: Los autores derivan una fórmula explícita para el número de matrices MDS ortogonales de $3 \times 3$ sobre $\mathbb{F}_{2^m}$ como $(2^m - 2)(2^m - 3)(2^m - 4)$.
  • MDS Semi-Ortogonales: Aprovechando el vínculo estructural, derivan el conteo para matrices MDS semi-ortogonales de $3 \times 3$ como $(2^m - 1)^5(2^m - 2)(2^m - 3)(2^m - 4)$.
  • MDS Semi-Involutorias: El artículo proporciona una derivación directa para el conteo de matrices MDS semi-involutorias de $3 \times 3$, confirmando la fórmula $(2^m - 1)^5(2^m - 2)(2^m - 4)$. Esto sirve como una alternativa a otras pruebas encontradas en la literatura.
• Intersección de Propiedades: Los autores caracterizan las matrices que son tanto semi-involutorias como semi-ortogonales. Demuestran que para matrices de $3 \times 3$, cualquier matriz semi-involutoria de la forma $M_1$ es necesariamente simétrica, lo que implica que el conteo de matrices que poseen ambas propiedades es idéntico al conteo de matrices semi-involutorias.
• Enumeración de Matrices 4×4: El estudio se extiende a matrices de $4 \times 4$. Los autores computan el número de matrices MDS semi-involutorias para $m = 3, \dots, 8$ y matrices ortogonales/semi-ortogonales para $m=3, 4$. También identifican matrices MDS ortogonales ligeras de orden 4 basadas en conteos de puertas d-XOR, encontrando conteos óptimos de 64 sobre $\mathbb{F}_{2^3}$ y 72 sobre $\mathbb{F}_{2^4}$.
• Estructura General: Se deriva una forma general para matrices ortogonales de $n \times n$ sobre $\mathbb{F}_{2^m}$, expresando la última fila y columna en términos de los elementos de la submatriz restante y restricciones de sumatoria específicas.

Significancia y Reivindicaciones
El artículo afirma proporcionar un marco unificado para comprender la enumeración de matrices MDS con restricciones estructurales específicas. Al cambiar el enfoque de la construcción hacia las relaciones estructurales, los autores demuestran que los conteos de las variantes generalizadas (semi-involutorias/semi-ortogonales) pueden derivarse directamente de los conteos de sus contrapartes convencionales.

Los autores afirman que su trabajo ofrece:

1. Derivaciones Alternativas: Una derivación más directa y concisa para las fórmulas de conteo de matrices MDS semi-involutorias y semi-ortogonales de $3 \times 3$ en comparación con las pruebas exhaustivas existentes.
2. Nuevos Datos de Enumeración: Conteos explícitos para matrices MDS ortogonales de $3 \times 3$ (previamente no establecidos en la literatura) y conteos extendidos para matrices de $4 \times 4$ sobre cuerpos finitos más grandes.
3. Perspectiva Teórica: Una prueba de que para matrices de $3 \times 3$, la intersección de las propiedades semi-involutoria y semi-ortogonal coincide con el conjunto de matrices semi-involutorias, una propiedad que no necesariamente se cumple para órdenes superiores (por ejemplo, $n \ge 4$).

El artículo concluye que estas interconexiones proporcionan un método sistemático para determinar el número de matrices MDS que satisfacen restricciones estructurales adicionales, consolidando fórmulas de enumeración explícitas para varias clases de matrices MDS de $3 \times 3$ y $4 \times 4$ con restricciones algebraicas.