Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

1. Problema y Contexto

El artículo aborda la vulnerabilidad de los sistemas de Criptografía Post-Cuántica (PQC) basados en el problema de Aprendizaje con Errores (LWE). LWE es fundamental para la seguridad de muchos esquemas modernos, pero su seguridad depende de la dificultad de recuperar un vector secreto $s$ a partir de pares ruidosos $(a, b = a \cdot s + \epsilon \mod q)$.

• El desafío: Los ataques de Aprendizaje Automático (ML) anteriores, como SALSA, han demostrado recuperar secretos con pesos de Hamming bajos (pocos bits no nulos) o secretos "esparcidos" (sparse). Sin embargo, estos ataques fallan sistemáticamente cuando el secreto tiene más de 3 bits "crueles" (cruel bits).
• La distinción Cruel vs. Fresco: Tras aplicar reducción de retículos (BKZ), el vector $a$ se divide en dos regiones:
  • Región "Cruel" (Cruel region): Las primeras coordenadas que permanecen sin reducir. Son difíciles de predecir para los modelos de ML si hay muchos bits activos.
  • Región "Fresca" (Cool region): Las últimas coordenadas que se reducen significativamente. Una vez conocidos los bits crueles, los bits frescos deberían ser fáciles de recuperar.
• Limitación actual: Los ataques ML previos se estancan en secretos con 3 bits crueles o menos, limitando su eficacia contra secretos más densos o de mayor peso de Hamming.

2. Metodología Propuesta

Los autores proponen una combinación de tres técnicas principales para superar las limitaciones de los ataques ML anteriores:

A. Conjuntos de Entrenamiento Grandes y Ejemplos Repetidos

• Hipótesis: Inspirados en trabajos previos sobre multiplicación modular, los autores proponen que entrenar modelos con ejemplos repetidos (repetir los mismos pares de datos múltiples veces durante el entrenamiento) y conjuntos de datos masivos permite al modelo aprender mejor la aritmética modular compleja.
• Implementación: Generaron hasta 400 millones de muestras sintéticas o reducidas mediante BKZ. Utilizaron un Transformer (arquitectura encoder-only) con embebimientos angulares para representar los datos modulares.
• Hallazgo clave: La repetición de datos no solo aumenta el volumen de entrenamiento, sino que modifica la ley de escalado de la dificultad del problema, permitiendo recuperar secretos con más de 3 bits crueles.

B. Recuperación de Bits "Frescos" mediante Regresión Escalonada (Stepwise Regression)

• Problema del método anterior: Los métodos previos usaban regresión lineal simple para recuperar los bits frescos una vez conocidos los crueles. Esto falla porque ignora la naturaleza modular (el producto punto "envuelve" alrededor de $q$) y acumula errores de covarianza.
• Solución: Introducen una técnica de Regresión Escalonada (Stepwise Regression):
  1. Se resta la contribución de los bits crueles conocidos.
  2. Se realiza una regresión lineal sobre los bits restantes.
  3. Se identifica el coeficiente más pequeño (normalizado), se asume que corresponde a un bit cero, y se elimina de la ecuación.
  4. Se repite el proceso iterativamente.
• Dual Stepwise Regression: Cuando la mayoría de los bits restantes son unos (en lugar de ceros), el algoritmo invierte el problema (dual) para recuperar los ceros restantes, alternando entre ambas estrategias.

C. Arquitectura del Modelo

• Se utiliza un Transformer con 4 capas.
• Mejora clave: Se introduce un embebimiento posicional binario que indica explícitamente si una coordenada pertenece a la región "cruel" o "fresca", mejorando la capacidad del modelo para distinguir entre ambas regiones.

3. Contribuciones Clave

1. Superación del límite de 3 bits crueles: Demostraron que es posible recuperar secretos binarios y ternarios con hasta 8 bits crueles, superando la barrera de los trabajos anteriores.
2. Ley de Escalado Empírica: Definieron una ley de potencia que relaciona el número de intentos del modelo para recuperar el secreto ($A$) con la cantidad de datos ($D$) y la repetición ($R$):
   $$\ln(AR) = C_R - \alpha_R \ln(D)$$
   Donde $\alpha_R$ aumenta con la repetición, indicando que los datos repetidos son más eficientes que simplemente aumentar el tamaño del conjunto de datos único.
3. Uso de Datos Sintéticos: Validaron que los modelos entrenados con datos sintéticos (generados con la misma varianza que los datos reducidos por BKZ) logran el mismo rendimiento que los entrenados con datos reducidos costosos, lo que permite escalar experimentos sin el costo computacional de la reducción BKZ.
4. Mejora de la Regresión: Reemplazaron la regresión lineal estándar por regresión escalonada dual, logrando una recuperación mucho más robusta de los bits frescos en presencia de ruido modular.

4. Resultados Principales

Los autores evaluaron sus ataques en cuatro configuraciones de parámetros LWE ($n=256/512$, diferentes log$q$) comparándolos con trabajos previos como SALSA, VERDE, PICANTE y Cool & Cruel.

• Peso de Hamming Recuperado:
  • En la configuración $n=256, \log_2 q = 20$, recuperaron secretos con $h=70$ (vs. $h=33$ en VERDE).
  • En la configuración $n=512, \log_2 q = 41$, recuperaron secretos con $h=75$ (vs. $h=63$ en VERDE y $h=60$ en Cool & Cruel).
• Tasa de Éxito Global:
  • Para $n=256, \log_2 q = 20$ y $h=33$, su método recupera el 98% de los secretos, mientras que VERDE solo recupera el 33%.
  • Para $n=512, \log_2 q = 41$ y $h=63$, su método recupera el 91% de los secretos, frente al 15% de VERDE.
• Eficiencia de Datos: La repetición de datos (hasta 50x) fue crucial. Por ejemplo, para recuperar secretos con 4 bits crueles en $n=512$, se necesitaron solo 20 millones de ejemplos repetidos 10 veces, mientras que sin repetición se requerían conjuntos de datos mucho más grandes.

5. Significado e Implicaciones

• Seguridad de PQC: Este trabajo demuestra que los secretos "esparcidos" (sparse) y de pequeño tamaño, a menudo elegidos por su eficiencia en cifrado homomórfico, son más vulnerables de lo que se pensaba. Los límites de seguridad actuales podrían estar sobreestimados para ciertos parámetros.
• Estrategia de Ataque: Establece que la combinación de grandes volúmenes de datos + repetición + técnicas estadísticas avanzadas (regresión escalonada) es una vía viable para romper instancias de LWE que antes se consideraban seguras contra ataques ML.
• Escalabilidad: La demostración de que los datos sintéticos pueden reemplazar a los datos reducidos por BKZ en la fase de entrenamiento sugiere que los ataques ML pueden escalar a problemas de mayor dimensión sin los costos computacionales prohibitivos de la reducción de retículos.
• Conclusión: La comunidad de criptografía debe reconsiderar los parámetros de seguridad para esquemas basados en LWE con secretos pequeños o esparcidos, integrando estas nuevas capacidades de ataque en los estándares de evaluación.

En resumen, el artículo rompe la barrera de los 3 bits crueles en ataques ML a LWE mediante una estrategia de "fuerza bruta inteligente" (datos masivos y repetidos) combinada con una recuperación estadística refinada (regresión escalonada), logrando tasas de éxito significativamente superiores a los métodos del estado del arte.