Pruebas de seguridad y reducciones en esquemas basados en retículos

Una prueba de seguridad de un esquema criptográfico es un argumento matemático formal que demuestra que vulnerar el esquema implica resolver un problema difícil subyacente. La prueba no garantiza una seguridad absoluta; demuestra que cualquier adversario eficiente contra el esquema puede convertirse en un algoritmo eficiente para resolver el problema difícil. Si el problema difícil es intratable, el esquema es seguro.

La prueba fundamental de Regev, publicada en 2005, demuestra que un algoritmo de tiempo polinómico que resuelva el LWE decisional puede utilizarse para resolver GapSVP (problema del vector más corto con brecha) en el peor caso sobre retículos n-dimensionales. La reducción es cuántica: utiliza un procedimiento de muestreo cuántico para convertir un solucionador de LWE en un solucionador de problemas reticulares. Esto significa que LWE es, como mínimo, tan difícil como los problemas reticulares del peor caso en el contexto de la computación cuántica.

La reducción de Regev no es ajustada: los factores polinómicos de la reducción hacen que el nivel de seguridad garantizado por la prueba sea algo inferior al que sugieren los mejores ataques conocidos. Para seleccionar parámetros prácticos, los criptógrafos utilizan la seguridad concreta proporcionada por los mejores ataques conocidos, mediante el estimador de retículos, en lugar del límite teórico de la reducción, ya que esta es conservadora.

Un esquema de cifrado basado en LWE demuestra seguridad IND-CPA (indistinguibilidad frente a un ataque de texto plano elegido) mediante un argumento híbrido. La prueba demuestra que un distinguidor IND-CPA implica un distinguidor de LWE. En el primer híbrido, el texto cifrado real se sustituye por una cadena aleatoria uniforme; la indistinguibilidad se deriva del supuesto LWE. Esto proporciona una prueba de seguridad clara para el cifrado reticular básico.

La seguridad IND-CPA no es suficiente para los mecanismos de encapsulación de claves utilizados en TLS: necesitan seguridad IND-CCA2 (frente a ataques de texto cifrado elegido). La transformación de Fujisaki-Okamoto (FO) convierte cualquier esquema IND-CPA en un KEM IND-CCA2 en el modelo del oráculo aleatorio (ROM). ML-KEM aplica una variante de la transformación FO al cifrado subyacente basado en Module-LWE, proporcionando la seguridad CCA2 necesaria para su implementación en el mundo real.

El modelo del oráculo aleatorio (ROM) modela las funciones hash como funciones verdaderamente aleatorias. Muchas pruebas de seguridad, incluidas las de la transformación FO, requieren el ROM. En la práctica, las funciones hash como SHA-3 no son oráculos aleatorios verdaderos, por lo que las pruebas en el ROM no garantizan la seguridad en el modelo estándar. Sin embargo, la comunidad criptográfica acepta ampliamente las pruebas en el ROM como una evidencia sólida de seguridad.

Una prueba en el modelo estándar no hace ninguna idealización sobre las funciones hash y es estrictamente más sólida que una prueba en el ROM. La mayoría de los esquemas reticulares prácticos utilizan pruebas en el ROM porque las pruebas CCA2 en el modelo estándar para los KEM basados en retículos son mucho más complejas y producen parámetros concretos peores. NIST aceptó las pruebas basadas en el ROM para ML-KEM, considerándolas suficientes para los niveles de seguridad previstos.

La prueba de seguridad de ML-KEM consta de dos pasos. Primero, se demuestra que el cifrado subyacente basado en Module-LWE ofrece seguridad IND-CPA bajo el supuesto M-LWE. Segundo, la transformación de Fujisaki-Okamoto, específicamente las transformaciones T y U utilizadas en Kyber, eleva esta seguridad a IND-CCA2 en el ROM cuántico (QROM), que contempla adversarios que consultan el oráculo aleatorio en superposición.

El estimador de retículos desarrollado por Albrecht, Player y Scott es la herramienta estándar para calcular la seguridad concreta de los esquemas basados en LWE. Modela el coste de los mejores ataques reticulares conocidos (BKZ con cribado o enumeración) y devuelve una estimación de seguridad en bits para unos parámetros dados (n, q, sigma). La herramienta se actualiza periódicamente a medida que se publican nuevos algoritmos y modelos de costes de hardware.

El algoritmo Block Korkine-Zolotarev (BKZ) es el mejor algoritmo práctico de reducción de retículos. BKZ con tamaño de bloque beta encuentra vectores cortos con una complejidad aproximada de 2^{0.292*beta} operaciones de compuerta mediante los mejores algoritmos de cribado. Para ML-KEM-768, la seguridad clásica estimada es de unos 180 bits y la seguridad cuántica de unos 164 bits, muy por encima del objetivo de 192 bits.

Las pruebas de seguridad asintóticas demuestran que un esquema es seguro para parámetros suficientemente grandes, pero no especifican qué significa «suficientemente grandes» en la práctica. El análisis de seguridad concreta cubre esta carencia al estimar el coste real del mejor ataque para los parámetros elegidos. La estandarización poscuántica depende en gran medida del análisis de seguridad concreta, con parámetros seleccionados para resistir ataques en el hardware cuántico previsto durante un horizonte de 30 años.

¿Qué transformación se utiliza para elevar el cifrado reticular IND-CPA a seguridad IND-CCA2 en ML-KEM?

Las pruebas de seguridad de los esquemas reticulares reducen la seguridad del esquema a la dificultad de LWE o SVP. La reducción de Regev garantiza que LWE es, como mínimo, tan difícil como los problemas reticulares del peor caso. La transformación de Fujisaki-Okamoto eleva IND-CPA a IND-CCA2 en el ROM. La seguridad concreta se evalúa con el estimador de retículos utilizando modelos de complejidad de BKZ. Las brechas en el ajuste de las reducciones hacen que los parámetros prácticos dependan de las estimaciones del coste de los ataques, y no únicamente de los límites de las reducciones.