A New Class of Linear Codes

Resumen Técnico: Una Nueva Clase de Códigos Lineales

Planteamiento del Problema
El artículo aborda la construcción de códigos lineales sobre cuerpos finitos $\mathbb{F}_r$ con longitud $n$ y distancia relativa asintótica a $1/2$ (específicamente $d \approx n/2$). Si bien los códigos binarios con distancia mínima aproximadamente $n/2$ son fundamentales, la cota de Plotkin restringe el tamaño de tales códigos para que sea extremadamente pequeño cuando $d \ge n/2$. En el régimen donde $d < n/2$ pero $n - 2d = \Omega(\sqrt{n})$, las mejores construcciones conocidas han sido históricamente los códigos no lineales de Delsarte–Goethals. Estos códigos, aunque efectivos, sufren de tasas que decaen exponencialmente a medida que la longitud aumenta. Los autores pretenden construir códigos lineales que alcancen parámetros comparables o mejores, específicamente apuntando a una mejora exponencial en el tamaño del código (tasa) respecto a los códigos de Delsarte–Goethals, manteniendo el régimen de distancia relativa de $1/2$.

Metodología
Los autores introducen una construcción basada en la teoría de sumas de caracteres multiplicativos y curvas superelípticas, denominada Códigos de Sombra (Shadow Codes). La estrategia central consiste en:

1. Configuración del Cuerpo: Utilizar un cuerpo auxiliar $\mathbb{F}_q$ (donde $q$ es una potencia de un primo) para construir un código sobre un cuerpo base más pequeño $\mathbb{F}_r$ (donde $r$ es un primo que divide a $q-1$).
2. Curvas Superelípticas: Seleccionar una colección de polinomios irreducibles mónicos $P = \{p_1, \dots, p_L\}$ sobre $\mathbb{F}_q$.
3. Mapeo de Caracteres: Definir un mapeo donde las entradas de la palabra de código se determinan mediante la evaluación de un carácter multiplicativo $\chi_r$ de orden $r$ sobre productos de estos polinomios. Específicamente, para el vector de mensaje $(v_1, \dots, v_L) \in \mathbb{F}_r^L$, la entrada de la palabra de código en el índice $x \in \mathbb{F}_q$ viene dada por $\phi_r(\chi_r(\prod p_i(x)^{v_i}))$, donde $\phi_r$ es un isomorfismo que mapea las raíces de la unidad al grupo aditivo de $\mathbb{F}_r$.
4. Interpretación Geométrica: La "sombra" se refiere a la proyección de la curva superelíptica $y^r = f(x)$ (donde $f$ es el producto de los polinomios) sobre el eje x. Los ceros de la palabra de código corresponden a las coordenadas x donde $f(x)$ es una potencia $r$-ésima.
5. Concatenación: Para mejorar aún más los parámetros, los autores proponen concatenar estos códigos de Sombra con códigos de Reed-Solomon (RS).

Contribuciones Clave y Resultados

• Construcción de Códigos de Sombra: El artículo demuestra la existencia de códigos $\mathbb{F}_r$-lineales con longitud $n=q$, dimensión $k \approx q^{1/2-\epsilon}$, y distancia mínima $d \ge \frac{r-1}{r}q - O(q^{1-\epsilon})$.

  • Teorema I.1: Establece la existencia de estos códigos para cualquier $\epsilon \in (0, 1/2)$ y un $q$ suficientemente grande.
  • Corolario I.2: Se especializa a códigos binarios ($r=2$), produciendo parámetros $[q, \lfloor q^{1/2-\epsilon} \rfloor, d]$ con $d \ge q/2 - 2q^{1-\epsilon}$.

• Mejora Exponencial sobre los Códigos de Delsarte–Goethals:

  • Los autores demuestran que para el régimen $n - 2d = \Omega(\sqrt{n})$, sus códigos de Sombra lineales tienen un tamaño exponencialmente mayor que los códigos de Delsarte–Goethals.
  • Proposición III.2: Muestra que para una secuencia de parámetros, la razón entre el logaritmo del tamaño del código de Sombra y el código de Delsarte–Goethals es $\Omega(2^{m\delta/2}/m^2)$, confirmando una ganancia exponencial. A diferencia de los códigos de Delsarte–Goethals, los nuevos códigos son lineales y poseen un algoritmo de decodificación.

• Impulso por Concatenación:

  • Concatenación RS-Sombra (Teorema V.1): Al concatenar un código de Reed-Solomon con un código de Sombra, los autores logran un código de longitud $N = q^{n+1}$ con dimensión $N^{1 - \frac{1}{2n+2} - \frac{2\epsilon}{n+1}}$ y distancia relativa asintótica a $1/2$.
  • Comparación con RS-RM: El artículo argumenta que reemplazar el código interno de Reed-Muller (RM) en las concatenaciones estándar con un código de Sombra produce una tasa significativamente mayor para el mismo régimen de longitud y distancia, ya que los códigos de Sombra soportan dimensiones mayores que los códigos RM de primer orden.

• Cuadrado de Códigos de Sombra y Criptografía:

  • Teorema VI.1: Demuestra que el cuadrado de un código de Sombra (bajo el producto de Schur) tiene dimensión $L(L+1)/2$, siempre que $q$ sea suficientemente grande en relación con la dimensión $L$. Esto imita el comportamiento de los códigos aleatorios.
  • Significado: Los códigos con cuadrados de alta dimensión son valiosos para aplicaciones criptográficas (por ejemplo, esquemas de firma) ya que resisten ciertos ataques algebraicos. En contraste, el artículo muestra (Teorema VI.4) que el cuadrado de un código concatenado RS-RM tiene una dimensión que es insignificante en comparación con el límite universal, lo que lo hace menos adecuado para tales aplicaciones.

• Algoritmo de Decodificación:

  • Sección VII: El artículo presenta un algoritmo de decodificación eficiente para códigos de Sombra binarios basado en el método de Swastik Kopparty. Esto implica la recuperación de un polinomio de mensaje libre de cuadrados a partir de evaluaciones ruidosas del carácter cuadrático, utilizando álgebra lineal y factorización de polinomios.

• Aplicación a la Teoría de Números:

  • Sección IV: Los autores aplican cotas de la teoría de códigos (Plotkin y McEliece) para derivar nuevos resultados sobre sumas exponenciales, estableciendo específicamente cotas inferiores para el valor máximo de ciertas sumas de caracteres sobre cuerpos finitos.

Significancia y Reivindicaciones
El artículo afirma proporcionar una prueba constructiva de la existencia de una nueva clase de códigos lineales que superan a los códigos no lineales de Delsarte–Goethals en el régimen de distancia relativa $1/2$. La principal significancia radica en la mejora exponencial en el tamaño del código (tasa) manteniendo la linealidad y proporcionando un algoritmo de decodificación explícito. Además, el trabajo destaca cómo la estructura algebraica de estos códigos (específicamente el comportamiento de sus cuadrados) los convierte en candidatos prometedores para aplicaciones criptográficas, distinguiéndolos de otras familias de códigos concatenados como RS-RM. Este trabajo también tiende un puente entre la teoría de códigos y la teoría de números al derivar nuevas cotas sobre sumas de caracteres.