Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

Aquí presento un resumen técnico detallado del artículo "Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs" (Ataques a LWE y LPN dispersos con nuevos compromisos entre muestra y tiempo), escrito por Shashwat Agrawal, Amitabha Bagchi y Rajendra Kumar del Instituto Indio de Tecnología de Delhi.

---

1. Introducción y Problema

El trabajo se centra en la complejidad computacional de dos problemas fundamentales en criptografía post-cuántica: Learning With Errors (LWE) y Learning Parity with Noise (LPN), específicamente en sus variantes dispersas (sparse).

• Contexto: En LWE/LPN estándar, los vectores de coeficientes se eligen uniformemente al azar. En la versión dispersa, los vectores de coeficientes tienen solo $k$ entradas no nulas (donde $k \ll n$). Esta restricción se utiliza para mejorar la eficiencia en la generación de claves y el almacenamiento, pero plantea dudas sobre si mantiene la misma dureza que la versión estándar.
• El Problema: Dado un conjunto de muestras $(a, b)$ donde $a$ es un vector disperso, determinar si provienen de una distribución "plantada" (donde $b = \langle a, s \rangle + e$) o de una distribución uniforme aleatoria.
• Estado del Arte:
  • Para $q=2$ (LPN/LWE binario), existen ataques basados en el Método de Kikuchi (Wein et al., 2019) y mejoras recientes (Gupta et al., 2026) que utilizan grafos para encontrar estructuras combinatorias.
  • Para moduli grandes ($q > 2$), el problema estaba menos explorado. Un trabajo reciente de Jain, Lin y Saha (JLS24) sugirió que el LWE disperso con $k \ge \Omega(\log n)$ y muestras polinomiales es tan duro como el LWE estándar, basándose en ataques que requerían tiempo exponencial.

2. Metodología: Generalización del Método de Kikuchi

Los autores extienden el método de Kikuchi, originalmente diseñado para $q=2$, para manejar moduli $q$ más altos. La estrategia central consiste en transformar el problema de distinguir instancias aleatorias de plantadas en un problema de análisis espectral o combinatorio sobre un Grafo de Kikuchi.

A. Construcción del Grafo de Kikuchi ($K_l(I)$)

1. Transformación a Ecuaciones de Producto: Las ecuaciones lineales sobre $\mathbb{Z}_q$ se reescriben como ecuaciones de producto sobre las raíces $q$-ésimas de la unidad ($\Omega_q = \{1, \omega_q, \dots, \omega_q^{q-1}\}$).
2. Espacio de Alta Dimensión: Para convertir una ecuación $k$-dispersa en un sistema de ecuaciones 2-dispersas (que forman un grafo), se "eleva" el problema a un espacio de dimensiones $l \times [q]^l$ (donde $l \ge k/2$ es un parámetro de compromiso).
   • A diferencia del caso $q=2$, para $q>2$ es necesario codificar tanto los índices como los coeficientes no nulos.
   • Esto genera un grafo dirigido donde los vértices son subconjuntos de pares (índice, coeficiente) y las aristas representan las restricciones.
3. Simetrización: Para facilitar el análisis espectral, el grafo se construye de manera que si existe una arista $T_1 \xrightarrow{b} T_2$, también existe $T_2 \xrightarrow{b^*} T_1$, haciendo la matriz de adyacencia hermítica.

B. Dos Enfoques de Ataque

Los autores proponen dos algoritmos distintos basados en la misma estructura de grafo:

1. Método Espectral (Generalización de Wein et al.)

• Idea: Calcular la norma espectral (el valor propio máximo en magnitud) de la matriz de adyacencia del grafo de Kikuchi.
• Lógica:
  • En una instancia aleatoria, la norma espectral esperada es baja (cercana a 0).
  • En una instancia plantada, la norma espectral esperada es alta (proporcional al grado promedio del grafo y a la correlación del ruido).
• Herramientas: Se utiliza la desigualdad de Bernstein para matrices (Matrix Bernstein) para acotar las colas de la distribución de la norma espectral en ambos casos.
• Ventaja: Funciona para cualquier distribución de ruido simétrica y concentrada en cero, sin asumir que $q$ es primo.

2. Método de Cubrimiento $q$-ario (Generalización de Gupta et al.)

• Idea: Encontrar "caminos cerrados no triviales" en el grafo de Kikuchi. Estos caminos corresponden a cubrimientos $q$-arios (multiconjuntos de restricciones cuya suma de coeficientes es $0 \mod q$).
• Lógica:
  • Para LPN: Se analiza el producto de los términos del lado derecho a lo largo del camino. En el caso plantado, este producto tiene una esperanza no nula debido a la estructura del ruido uniforme en $\Omega_q \setminus \{1\}$. En el caso aleatorio, la esperanza es 0. Se utiliza un resultado de anti-concentración para polinomios multilineales para distinguir los casos.
  • Para LWE: Dado que el ruido gaussiano no permite el mismo análisis de producto, se utiliza la acotación del error. Si se encuentra un cubrimiento $c$ tal que $c^T A = 0$, entonces $c^T b = c^T e$. Si el error es acotado, $|c^T b|$ será pequeño en el caso plantado, mientras que en el caso aleatorio será uniforme en $\mathbb{Z}_q$.
• Requisitos: Este método requiere que $q$ sea primo y, para LWE, que $q$ sea suficientemente grande en relación con el ancho del ruido.

3. Contribuciones Clave y Resultados

El artículo establece nuevos compromisos entre la complejidad de muestras ($m$) y la complejidad de tiempo ($T$) para resolver LWE/LPN dispersos sobre moduli grandes.

Teoremas Principales (Resumen Informal)

Para una dimensión $n$, parámetro de dispersión $k$, y un parámetro de compromiso $l$ ($k/2 \le l \le n$):

1. Ataque Espectral (LWE y LPN):

   • Tiempo: $\tilde{O}\left( \binom{n}{l} q^l \right)$.
   • Muestras: $m \ge \tilde{O}\left( \left(\frac{n}{l}\right)^k \right)$ (dependiendo de si $q$ es pequeño o grande).
   • Ventaja: No requiere que $q$ sea primo y funciona con distribuciones de ruido generales.

2. Ataque de Cubrimiento $q$-ario (LWE y LPN):

   • Tiempo: $\tilde{O}\left( \sqrt{\binom{n}{l} q^l} \cdot (n/l)^k \right)$ (aproximadamente una aceleración cuadrática sobre el método espectral para el mismo número de muestras cuando $l \gg k$).
   • Muestras: Similar al método espectral.
   • Ventaja: Funciona incluso si los lados izquierdos de las ecuaciones no son uniformemente aleatorios (caso de peor caso).

Resultados Específicos sobre la Dureza

• Los autores muestran que si se permite un tiempo de $2^{\delta n}$ (para $\delta$ arbitrariamente pequeño), se requieren muestras polinomiales o casi polinomiales.
• Esto cuestiona la conjetura de dureza propuesta por Jain, Lin y Saha (JLS24), que sugería que el LWE disperso con $k = \Omega(\log n)$ y $m = \text{poly}(n)$ era tan duro como el LWE estándar. Los resultados de este trabajo indican que, bajo ciertos parámetros, el LWE disperso puede ser resuelto en tiempo sub-exponencial con muestras polinomiales, estrechando la brecha de seguridad.

4. Comparación de Métodos

Característica	Método Espectral	Método de Cubrimiento $q$-ario
Tiempo	$\tilde{O}(\binom{n}{l} q^l)$	$\tilde{O}(\sqrt{\binom{n}{l} q^l} \cdot (n/l)^k)$
Aceleración	Estándar	Casi cuadrática sobre el método espectral
Requisito de $q$	Ninguno (funciona para cualquier $q$)	$q$ debe ser primo (y grande para LWE)
Distribución de Lado Izquierdo	Requiere uniformidad	Funciona con distribuciones arbitrarias
Distribución de Ruido	General (concentrada en 0)	LWE: Ruido acotado; LPN: Uniforme en no-ceros
Aceleración Cuántica	Sí (hasta cuártica)	Desconocida

5. Significado e Impacto

1. Refinamiento de la Seguridad: El trabajo proporciona un análisis más fino de la seguridad de los esquemas criptográficos basados en LWE/LPN dispersos. Sugiere que la dispersión, aunque mejora la eficiencia, introduce vulnerabilidades que pueden ser explotadas con menos muestras de las esperadas si se permite un tiempo de cálculo sub-exponencial.
2. Generalización de Técnicas: Extiende las técnicas combinatorias y espectrales de $q=2$ a moduli generales, lo cual es crucial para la implementación práctica de criptografía avanzada (como FHE) que a menudo utiliza moduli grandes.
3. Validación de Conjeturas: El resultado sugiere que la conjetura de dureza de JLS24 es "casi" cierta, pero que el margen de seguridad es más estrecho de lo que se pensaba, especialmente cuando la dispersión $k$ es pequeña o el número de muestras es ligeramente superior a lo polinomial.
4. Herramientas Nuevas: La introducción de la noción de "cubrimiento $q$-ario" y su conexión con caminos cerrados en grafos dirigidos abre nuevas vías para el análisis de problemas de satisfacción de restricciones sobre anillos finitos.

En resumen, el artículo demuestra que los problemas de aprendizaje con errores dispersos sobre moduli grandes son más vulnerables a ataques basados en grafos de lo que se creía, ofreciendo nuevos algoritmos que equilibran mejor el tiempo de ejecución y la cantidad de muestras necesarias, desafiando así las suposiciones actuales sobre la seguridad de ciertas optimizaciones de eficiencia en criptografía post-cuántica.