MDS matrices from skew polynomials with automorphisms and derivations

Resumen Técnico: Matrices MDS a partir de Polinomios Sesgados con Automorfismos y Derivaciones

Planteamiento del Problema
Las matrices de Distancia Máxima Separable (MDS) son fundamentales para el diseño de capas de difusión en criptografía de clave simétrica, proporcionando una resistencia óptima contra el criptoanálisis diferencial y lineal. Si bien las matrices circulantes y recursivas son ampliamente estudiadas debido a sus descripciones algebraicas eficientes y propiedades de implementación, las construcciones existentes a menudo enfrentan limitaciones. Específicamente, las matrices circulantes clásicas de orden par no pueden ser simultáneamente MDS e involutorias (autoinversas), una propiedad altamente deseable para reducir los costos de implementación en primitivas criptográficas. Generalizaciones previas utilizando anillos de polinomios sesgados con automorfismos (matrices $\theta$-circulantes) han abordado algunos de estos problemas, pero a menudo permanecen confinadas a campos finitos específicos o producen únicamente matrices cuasi-involutorias. Además, la incorporación de derivaciones en estas estructuras algebraicas para generalizar aún más la clase de matrices MDS construibles no ha sido explorada plenamente.

Metodología
Los autores desarrollan sus construcciones dentro del marco de los anillos de polinomios sesgados $F_q[X; \theta, \delta]$, donde $F_q$ es un campo finito, $\theta$ es un automorfismo de $F_q$ y $\delta$ es una $\theta$-derivación. La multiplicación en este anillo no conmutativo se define por la regla $Xa = \theta(a)X + \delta(a)$.

El artículo procede a través de los siguientes pasos metodológicos:

1. Definición de Matrices $\delta\theta$-Circulantes: Los autores introducen una nueva clase de matrices estructuradas, denominadas matrices $\delta\theta$-circulantes, que generalizan las matrices circulantes y $\theta$-circulantes clásicas al incorporar la $\theta$-derivación $\delta$. La estructura de estas matrices se analiza mediante su asociación con transformaciones lineales en el anillo cociente $F_q[X; \theta, \delta] / \langle X^m - 1 \rangle$.
2. Caracterización Algebraica: Se derivan condiciones necesarias y suficientes para que estas matrices satisfagan la propiedad MDS y la propiedad involutoria ($A^2 = I$). Esto implica el análisis del peso de los polinomios en el anillo sesgado y la relación entre el polinomio generador y la matriz resultante.
3. Construcciones Cuasi Recursivas: El estudio se extiende a matrices MDS cuasi recursivas, definidas mediante un producto específico de matrices que involucra potencias del automorfismo y la derivación. Los autores se centran en las matrices compañeras asociadas con polinomios sesgados mónicos.
4. Aplicación del Producto de Hadamard: El artículo utiliza el producto de Hadamard de polinomios para generar nuevas familias de matrices MDS a partir de otras existentes, preservando la propiedad MDS bajo condiciones específicas.

Contribuciones Clave y Resultados

• Matrices $\delta\theta$-Circulantes:

  • El artículo define las matrices $\delta\theta$-circulantes y establece una correspondencia entre estas matrices y las transformaciones lineales en el anillo de polinomios sesgados.
  • El Teorema 2 proporciona una condición necesaria y suficiente para que una matriz $\delta\theta$-circulante sea MDS: para cualquier polinomio no nulo $Q_1(X)$, la suma de los pesos de $Q_1(X)$ y $Q_1(X)h(X) \pmod{X^m-1}$ debe ser al menos $m+1$.
  • El Teorema 3 establece la condición para que una matriz $\delta\theta$-circulante sea involutoria, vinculándola con el producto del polinomio generador y su inverso en el anillo sesgado.
  • Los autores señalan que, si bien las matrices $\theta$-circulantes (donde $\delta=0$) pueden producir matrices MDS involutorias de orden par, la introducción de $\delta$ expande la clase de matrices construibles.

• Matrices MDS Involutorias Cuasi Recursivas:

  • Una contribución central es la construcción de matrices MDS cuasi recursivas que son estrictamente involutorias (no solo cuasi-involutorias).
  • El Teorema 5 demuestra que para una elección específica del automorfismo $\theta(a) = a^{q^2}$ y un polinomio $g(X)$ que genera un código MDS, la matriz cuasi recursiva resultante $N_g$ satisface $N_g^2 = I_m$. Esto representa una mejora estricta respecto a resultados previos (p. ej., Cauchois et al. [15]) que producían matrices cuasi-involutorias limitadas a clases de campos restringidas.
  • El Teorema 6 extiende el criterio para matrices MDS recursivas al entorno cuasi recursivo, relacionando la propiedad MDS con el peso de los múltiplos por la derecha del polinomio generador.

• Generación de Nuevas Matrices:

  • El Teorema 8 muestra que, si un polinomio $g(X)$ produce una matriz MDS cuasi recursiva, entonces su potencia de Hadamard $(g(X))^{\diamond 2t}$ también produce una matriz MDS cuasi recursiva. Esto permite la generación de múltiples nuevas matrices MDS a partir de un único polinomio semilla.
  • El Teorema 7 establece que el polinomio recíproco de un generador para matrices MDS involutorias también genera matrices MDS involutorias.

Significancia y Reivindicaciones
El artículo sostiene que su principal significancia radica en la generalización de las construcciones de matrices MDS existentes mediante la inclusión de $\theta$-derivaciones. Específicamente:

• Introduce las matrices $\delta\theta$-circulantes como una clase más amplia que las matrices $\theta$-circulantes, ofreciendo un entorno algebraico unificado tanto para las estructuras circulantes como para las recursivas.
• Proporciona una construcción para matrices MDS cuasi recursivas involutorias de orden par, abordando una limitación en la literatura previa donde tales matrices eran o bien inexistentes en el entorno clásico o solo cuasi-involutorias en el entorno sesgado. Esto es significativo para la eficiencia criptográfica, ya que las matrices involutorias eliminan la necesidad de implementaciones de inversión separadas.
• El trabajo ofrece criterios explícitos para las propiedades MDS e involutorias, facilitando la construcción sistemática de tales matrices.

Los autores reconocen que la caracterización completa de las matrices $\delta\theta$-circulantes MDS sigue siendo un problema abierto, particularmente cuando el parámetro $\beta$ (que define la derivación) no pertenece al campo fijo del automorfismo. También plantean la cuestión de si estas matrices poseen propiedades de ortogonalidad como una dirección para trabajos futuros.