El mundo de la seguridad postcuántica se ha visto sacudido por un reciente trabajo científico presentado por el investigador de Amazon Web Services (AWS), Daniel Simon. En un nuevo preprint, describe un algoritmo cuántico que, según afirma, es capaz de resolver problemas matemáticos clave que subyacen a los estándares postcuánticos modernos con complejidad polinómica, es decir, su tiempo de ejecución crece como una potencia del tamaño del problema, no exponencialmente como se pensaba anteriormente.

Si este resultado resulta ser correcto, podría redefinir radicalmente nuestra comprensión de la resiliencia de la criptografía de retículos frente a la computación cuántica. Sin embargo, es importante subrayar: el documento no contiene un ataque práctico contra los estándares vigentes, como ML-KEM (mecanismo de encapsulación de claves) o ML-DSA (firmas digitales). Se trata de un avance teórico que aún está por verificar.

La esencia del algoritmo y su relación con los retículos

Simon, conocido por su algoritmo homónimo de la década de 1990, que fue precursor del famoso algoritmo de Shor, se ha centrado en su nuevo trabajo en el llamado problema de clases laterales diedrales (Dihedral Coset Problem, DCP). En términos simples, una computadora cuántica recibe un conjunto de estados vinculados y debe identificar el valor oculto entre ellos. La DCP en sí no se utiliza directamente para el cifrado, pero ya a principios de la década de 2000, el matemático Oded Regev demostró que una solución eficiente de la DCP permitiría atacar ciertas variantes de problemas en retículos multidimensionales, incluidos el Problema del Vector Más Corto (SVP) y el de Aprendizaje con Errores (LWE).

La principal limitación del enfoque de Regev residía en la necesidad de una herramienta idealizada para resolver otra tarea compleja. Simon afirma haber logrado sortear este obstáculo realizando la transformación necesaria directamente en una computadora cuántica. Esto potencialmente abre el camino hacia una resolución acelerada de variantes estructuradas de LWE, sobre las cuales se construyen los estándares del NIST adoptados en 2024.

El pánico es prematuro: lo que queda fuera del foco

A pesar de los titulares llamativos, el trabajo de Simon no demuestra el descifrado de ML-KEM ni la falsificación de la firma ML-DSA. El investigador no atacó parámetros criptográficos específicos, y su algoritmo no incluye una estimación del número de qubits lógicos, compuertas cuánticas u operaciones de corrección de errores necesarias para una implementación práctica. Además, LWE es toda una familia de problemas, y un resultado para una clase no se transfiere automáticamente a todas las variantes estructuradas utilizadas en la industria.

En la comunidad científica ya ha habido precedentes en los que afirmaciones destacadas sobre algoritmos cuánticos polinómicos para retículos no superaron la verificación. Por ejemplo, en 2024, el investigador Yilei Chen afirmó un avance similar, pero pocos días después se encontró un error fatal en su demostración, y retiró sus conclusiones. Actualmente, no hay consenso independiente sobre el trabajo de Simon, y este es el principal indicador de que es demasiado pronto para sacar conclusiones.

Mi análisis: Este preprint es una señal importante para la industria, pero no un motivo de pánico. Subraya la fragilidad de nuestros modelos teóricos de seguridad actuales. Incluso si el algoritmo de Simon resulta ser correcto, faltan décadas para una amenaza práctica. Sin embargo, la comunidad criptográfica debería acelerar la transición hacia esquemas híbridos y la diversificación de algoritmos postcuánticos, para no poner toda la seguridad sobre una única base matemática.