The Star Product of Uniformly Random Codes

Resumen Técnico: El producto estrella de códigos uniformemente aleatorios

Planteamiento del problema
Este artículo investiga la dimensión esperada del producto estrella (también conocido como producto de Schur o de Hadamard) de dos códigos lineales, independientes y uniformemente aleatorios, $C_1$ y $C_2$, sobre un cuerpo finito $\mathbb{F}_q$. Los códigos tienen dimensiones prescritas $k_1$ y $k_2$ y longitud $n$. Si bien el producto estrella es una operación fundamental en la teoría de códigos con aplicaciones en corrección de errores cuánticos, recuperación de información privada (PIR) y multiplicación de matrices distribuida segura (SDMM), la dimensión del producto estrella de dos códigos aleatorios no es trivial de determinar. Trabajos previos, como [19], estimaron esta dimensión analizando la independencia lineal de matrices de rango 1, estableciendo que la dimensión esperada es igual a $\min\{n, k_1k_2\}$ con alta probabilidad bajo regímenes de parámetros restringidos. Este artículo tiene como objetivo proporcionar un análisis más general y explícito de la dimensión esperada y su varianza, extendiéndose más allá de esos regímenes restringidos.

Metodología
Los autores establecen una correspondencia entre el producto estrella de dos códigos y la evaluación de formas bilineales. Específicamente, si $C_1$ y $C_2$ tienen matrices generadoras $G_1$ y $G_2$, el producto estrella $C_1 \star C_2$ se identifica como la imagen de un mapa lineal $\psi_{G_1, G_2}$ que actúa sobre el espacio de formas bilineales $B = \text{Bil}(\mathbb{F}_q^{k_1}, \mathbb{F}_q^{k_2})$. La dimensión del producto estrella está dada por $k_1k_2 - \dim(\ker \psi_{G_1, G_2})$.

Para analizar la dimensión esperada, los autores se centran en calcular el tamaño esperado del núcleo, $\mathbb{E}[|\ker \psi_{C_1, C_2}|]$. Utilizan un modelo probabilístico donde los códigos se generan eligiendo las últimas $n-k$ columnas de una matriz generadora sistemática de forma uniforme al azar. El análisis involucra:

1. Combinatoria enumerativa: Contar el número de formas bilineales (representadas como matrices) de un rango $r$ específico que se anulan en las columnas de las matrices generadoras. Esto requiere contar matrices con diagonales cero y patrones de ceros específicos.
2. Fórmulas explícitas: Derivar una fórmula explícita para el tamaño esperado del núcleo utilizando coeficientes $q$-binomiales y principios de inclusión-exclusión (Lema 3.5 y Teorema 3.9).
3. Análisis asintótico: Investigar el comportamiento de estas fórmulas a medida que el tamaño del cuerpo $q \to \infty$ y a medida que las dimensiones de los códigos $k_1, k_2 \to \infty$ bajo condiciones de crecimiento específicas.
4. Análisis de la varianza: Utilizar las cotas derivadas sobre el tamaño esperado del núcleo para acotar superiormente la varianza de la dimensión del producto estrella.

Contribuciones clave y resultados

1. Cota inferior explícita: El artículo proporciona una fórmula explícita para el tamaño esperado del núcleo del mapa de evaluación, lo que ofrece una cota inferior explícita para la dimensión esperada del producto estrella para todas las elecciones de parámetros (Corolario 3.11). Este enfoque difiere de los análisis previos de matrices de rango 1 al ofrecer un conteo combinatorio directo del núcleo.

2. Asintótica en el tamaño del cuerpo ($q \to \infty$):

   • Los autores demuestran que, a medida que el tamaño del cuerpo $q$ tiende a infinito, la dimensión esperada del producto estrella alcanza asintóticamente su valor máximo posible, $\min\{n, k_1k_2\}$, independientemente de la relación entre $k_1$ y $k_2$ (Corolario 4.2).
   • Específicamente, si $k_1k_2 < n$, el tamaño esperado del núcleo tiende a 1; si $k_1k_2 = n$, tiende a 2; y si $k_1k_2 > n$, diverge.
   • Se muestra que la varianza de la dimensión decae asintóticamente a 0, con tasas que dependen de si $k_1k_2 < n$ o $k_1k_2 \ge n$ (Proposición 4.3).

3. Asintótica en las dimensiones de los códigos ($k_1, k_2 \to \infty$):

   • Bajo condiciones de crecimiento "admisibles" (donde $k_1$ y $k_2$ crecen estrictamente de forma monótona y $k_1k_2$ no crece demasiado rápido respecto a $q^{k_1}$), el artículo demuestra que el tamaño esperado del núcleo se estabiliza (Teorema 5.7).
   • En consecuencia, la dimensión esperada del producto estrella alcanza $\min\{n, k_1k_2\}$ con alta probabilidad a medida que las dimensiones aumentan (Corolario 5.12).
   • La varianza se muestra decreciente asintóticamente bajo estas condiciones, decayendo al menos exponencialmente si $n < k_1k_2$ o si la brecha $n - k_1k_2$ crece linealmente (Proposición 5.14).

4. Comparación con trabajos previos: Los resultados se comparan con el enfoque de matrices de rango 1 de [19]. Los autores señalan que sus resultados cubren un rango más amplio de regímenes de parámetros, particularmente para tamaños de cuerpo más grandes $q \ge 3$, donde sus cotas sobre el crecimiento de las dimensiones son estrictamente más fuertes que las de [19] (Observación 5.13).

Significado e implicaciones
El artículo afirma que estos resultados tienen implicaciones directas en varias áreas:

• Recuperación de Información Privada (PIR): En esquemas de PIR basados en productos estrella, la tasa de recuperación está limitada por la dimensión del producto estrella. Los resultados sugieren que, si bien los códigos aleatorios alcanzan asintóticamente dimensiones de producto estrella máximas (lo que conduce a tasas de recuperación más bajas en comparación con códigos estructurados como GRS), sigue existiendo una probabilidad no despreciable sobre cuerpos pequeños (por ejemplo, $\mathbb{F}_2$) de muestrear pares de códigos con dimensiones sub-máximas. Esto implica que las búsquedas experimentales de pares de códigos aleatorios favorables para PIR son viables, especialmente en entornos libres de errores.
• Multiplicación de Matrices Distribuida Segura (SDMM): De manera similar a la PIR, el umbral de recuperación y la tolerancia a rezagos (stragglers) en SDMM dependen de la dimensión del producto estrella. Los hallazgos indican que las construcciones aleatorias típicamente no logran umbrales de recuperación asintóticamente bajos, pero es posible encontrar instancias prácticas con parámetros favorables sobre cuerpos pequeños.
• Corrección de Errores Cuánticos: El artículo analiza los códigos CSS-T binarios, que requieren $C_2 \subseteq C_1 \cap (C_1 \star C_1)^\perp$. Los resultados implican que para códigos uniformemente aleatorios de dimensión suficientemente grande, el producto estrella $C_1 \star C_1$ es probablemente grande, lo que obliga al complemento ortogonal a ser pequeño. Esto sugiere que construir códigos CSS-T de alta distancia usando un $C_1$ aleatorio es improbable, ya que el código cuántico resultante tendría una cota inferior débil en su distancia mínima.
• Criptoanálisis: La dimensión del producto estrella se utiliza como un diferenciador en criptografía basada en códigos (por ejemplo, contra códigos Goppa). El artículo señala que, si bien sus resultados confirman que los códigos aleatorios generalmente tienen dimensiones de producto estrella máximas (lo que los hace distinguibles de códigos estructurados como los Goppa, que tienen cuadrados más pequeños), los rangos de parámetros específicos analizados no amenazan actualmente la seguridad de los sistemas McEliece estándar. Sin embargo, la metodología abre la puerta al análisis de productos estrella de diferentes pares de códigos para explorar nuevos rangos de parámetros.

Conclusión
El artículo concluye que la dimensión esperada del producto estrella de dos códigos uniformemente aleatorios alcanza asintóticamente su máximo teórico a medida que el tamaño del cuerpo aumenta, y bajo condiciones de crecimiento específicas, a medida que las dimensiones de los códigos aumentan. La varianza desaparece en estos regímenes, indicando una concentración de la medida. Los autores identifican la derivación de cotas inferiores ajustadas para la varianza y el análisis de casos no asintóticos como problemas abiertos para trabajos futuros.