Function-Based Minimal Linear Codes over Galois Rings $\mathrm{GR}(p^{n}, \ell)$: Minimality Criteria and Infinite Constructions

Resumen Técnico: Códigos Lineales Mínimos sobre Anillos de Galois

1. Planteamiento del Problema

Los códigos lineales mínimos son fundamentales en criptografía, especialmente en esquemas de compartición de secretos, computación multipartita y verificación de secretos, donde la estructura de acceso depende de que los vectores de código mínimos correspondan a subconjuntos calificados mínimos.

Mientras que la teoría de códigos mínimos sobre campos finitos está bien establecida (con construcciones infinitas basadas en funciones por Wu et al.), la extensión a anillos finitos presenta desafíos algebraicos significativos. En particular, los anillos de Galois $GR(p^n, \ell)$ poseen una estructura más rica que incluye divisores de cero y una estructura de módulo no trivial, lo que complica la definición y caracterización de la minimalidad. El problema central de este trabajo es:

• ¿Cómo caracterizar rigurosamente la minimalidad de códigos lineales sobre $GR(p^n, \ell)$?
• ¿Cómo generalizar las construcciones basadas en funciones de campos finitos a este entorno de anillos, superando las dificultades introducidas por los divisores de cero y la estructura de cadena?

2. Metodología

Los autores emplean un enfoque algebraico estructural que combina la teoría de módulos, la dualidad de Frobenius y el análisis de la valuación $p$-ádica.

• Estructura del Anillo: Se utiliza la propiedad de que $GR(p^n, \ell)$ es un anillo de cadena finito y un anillo de Frobenius. Esto permite el uso de la dualidad perfecta: $(C^\perp)^\perp = C$.
• Clasificación de Vectores: Se introduce una distinción crucial entre palabras raíz (root words) y no-palabras raíz. Una palabra raíz es un vector que no es aniquilado por ningún escalar no nulo (equivalente a tener al menos una componente unidad). Los vectores no-raíz pertenecen al ideal maximal $\langle p \rangle$.
• Reducción a Palabras Raíz: Mediante el Teorema 17, se demuestra que para dimensiones $m \ge 2$, un código es mínimo si y solo si todas sus palabras raíz son mínimas. Esto reduce el problema global a un análisis local de la estructura de los módulos ortogonales de las palabras raíz.
• Construcción Basada en Funciones: Se generaliza el marco de Wu et al. [27]. Se define un código $C_f$ mediante una matriz generadora cuyas filas son evaluaciones de una función $f: GR(p^n, \ell)^m \to GR(p^n, \ell)$.
• Análisis de Casos: Se descompone el problema de minimalidad en cinco tipos de vectores de código (basados en si los coeficientes son unidades o divisores de cero y si el vector espacial es raíz o no). Para cada caso, se establecen condiciones de sincronización entre la función $f$ y formas lineales.

3. Contribuciones Clave

1. Caracterización Completa de Minimalidad:
   Se establece una condición necesaria y suficiente para que un código lineal de dimensión $m$ sobre $GR(p^n, \ell)$ sea mínimo. A diferencia de los campos, donde la minimalidad depende de la relación de soporte, aquí se demuestra que para $m \ge 2$, la minimalidad está determinada exclusivamente por el comportamiento de las palabras raíz y sus módulos ortogonales.

2. Criterios de Minimalidad para Códigos Basados en Funciones:
   Se generalizan los criterios de Wu et al. al contexto de anillos. Se identifican dos condiciones de sincronización críticas:

   • Para coeficientes unidad: $f(\beta) = w \cdot \beta$.
   • Para coeficientes divisores de cero ($d = p^r u$): $p^r f(\beta) = w \cdot \beta$.
     Estas condiciones reflejan la geometría sensible a la valuación del anillo.

3. Construcciones Infinitas:
   Se proponen familias infinitas de códigos mínimos sobre $GR(p^n, \ell)$ mediante la selección cuidadosa de funciones $f$ (incluyendo polinomios multivariados) que satisfacen las condiciones de sincronización para los cinco tipos de vectores raíz.

4. Límites de Longitud:
   Se derivan cotas inferiores explícitas para la longitud $k$ de un código mínimo de dimensión $m$ sobre $GR(p^n, \ell)$, extendiendo los resultados conocidos para $\mathbb{Z}_{p^n}$ y campos finitos.

4. Resultados Principales

• Teorema de Reducción (Teorema 17): Para $m \ge 2$, un código $C$ es mínimo si y solo si todas sus palabras raíz son mínimas. Esto implica que la estructura de torsión del anillo no introduce nuevas obstrucciones a la minimalidad más allá de las ya codificadas en las palabras raíz.
• Construcción de Códigos Óptimos (Proposición 22 y 24): Se construye un código mínimo explícito con longitud:
  $$k = \frac{m(m-1)}{2}(q^n + q^{n-1} - 2) + m$$
  donde $q = p^\ell$. Para el caso $m=2$, se demuestra que la longitud mínima es exactamente $k(2; GR(p^n, \ell)) = q^n + q^{n-1}$, generalizando un resultado conocido para $\mathbb{Z}_{p^n}$.
• Criterios para Polinomios (Teorema 45): Se identifican condiciones suficientes para que un polinomio multivariado $f$ (suma de monomios con soportes disjuntos y ciertas propiedades de exponentes) genere un código mínimo. Esto facilita la generación práctica de tales códigos.
• Generalización de Resultados de Campos: Cuando $n=1$, el anillo $GR(p, \ell)$ se reduce al campo finito $\mathbb{F}_q$, y los resultados del artículo coinciden exactamente con las construcciones y límites clásicos, validando la generalización.

5. Significado e Impacto

• Unificación Teórica: El trabajo proporciona un marco unificado que conecta la teoría de minimalidad, la dualidad de módulos sobre anillos de Frobenius y las construcciones basadas en funciones.
• Avance en Criptografía Post-Cuántica y Distribuida: Al extender la teoría de códigos mínimos a anillos de Galois, se habilita el diseño de nuevos esquemas de compartición de secretos y sistemas de autenticación que operan en entornos donde los anillos (y no solo los campos) son naturales, como en criptografía basada en retículos o infraestructuras descentralizadas.
• Resolución de Dificultades Algebraicas: El artículo supera el obstáculo de los divisores de cero demostrando que, mediante un análisis adecuado de la filtración de valuación y la reducción módulo $p$, la complejidad del anillo puede ser gestionada sistemáticamente.
• Nuevas Direcciones de Investigación: El trabajo abre problemas abiertos sobre la distribución de pesos de estos códigos, la construcción de códigos de pocos pesos y la extensión a anillos de Frobenius arbitrarios.

En conclusión, este artículo representa un avance significativo en la teoría de códigos sobre anillos, transformando la comprensión de la minimalidad en estructuras algebraicas más complejas y proporcionando herramientas constructivas robustas para aplicaciones criptográficas avanzadas.