El algoritmo cuántico de AWS desafía los fundamentos de la criptografía postcuántica.
La comunidad científica se ha visto sacudida por un nuevo trabajo de Daniel Simon, investigador de Amazon Web Services. El algoritmo cuántico presentado por él, según estimaciones preliminares, podría acelerar radicalmente la resolución de una serie de problemas matemáticos en los que se basa la criptografía postcuántica moderna. La tesis clave es que la complejidad temporal del algoritmo no crece exponencialmente, sino polinomialmente, lo que, de confirmarse, cambiaría las concepciones actuales sobre la resistencia de las construcciones reticulares a los ataques cuánticos.
Es importante subrayar: el documento no contiene ni un ataque práctico contra los estándares vigentes como ML-KEM y ML-DSA, ni siquiera un desciframiento teórico de sus parámetros reales. El trabajo de Simon, conocido por su algoritmo homónimo de los años 90 —predecesor del famoso algoritmo de Shor—, se centra en un problema más abstracto, conocido como Dihedral Coset Problem (DCP).
La esencia del avance matemático
El DCP no se utiliza directamente para proteger carteras o conexiones, pero es una piedra angular para la criptografía reticular. Ya a principios de los años 2000, Oded Regev demostró que una solución eficiente del DCP permitiría atacar ciertas variantes de problemas en retículas multidimensionales. Sin embargo, su enfoque dependía del uso de una herramienta idealizada e inexistente para otra operación computacional compleja. Simon afirma haber encontrado una manera de sortear esta limitación, realizando la transformación requerida directamente en un ordenador cuántico.
En combinación con trabajos anteriores, este algoritmo podría extenderse potencialmente a variantes del Shortest Vector Problem (SVP) y del Learning With Errors (LWE). En términos simples, el SVP consiste en buscar el vector más corto en una retícula multidimensional compleja, y el LWE consiste en recuperar un secreto a partir de un sistema de ecuaciones con «ruido» añadido deliberadamente. Precisamente en la dificultad de estos problemas se basan los estándares del NIST adoptados en 2024: el mecanismo de encapsulamiento de claves ML-KEM y el algoritmo de firma digital ML-DSA.
El pánico es prematuro
A pesar de los titulares llamativos que esta noticia podría generar, insto a la cautela. La investigación no demuestra el desciframiento de ML-KEM ni la falsificación de firmas ML-DSA. Además, LWE es toda una familia de problemas, y los estándares prácticos utilizan subvariedades especialmente estructuradas. El resultado para una clase de LWE no puede trasladarse automáticamente a todos los sistemas criptográficos.
En el preprint falta información críticamente importante: la estimación del número de cúbits lógicos, compuertas cuánticas y volumen de corrección de errores necesarios para ejecutar el algoritmo en tamaños criptográficamente significativos. Sin estos datos, hablar de una amenaza práctica es prematuro. La historia conoce ejemplos de declaraciones rimbombantes que se desmoronaron, como en 2024, cuando el investigador Yilei Chen afirmó tener un algoritmo polinomial para LWE, pero pocos días después se encontró un error fatal en su demostración.
Mi análisis: Este trabajo es un desafío intelectual importante que subraya que nuestra comprensión de la computación cuántica aún está en formación. Sin embargo, para la industria es más una señal para acelerar la transición hacia esquemas híbridos y diversificar los primitivos criptográficos, que un motivo de pánico. Probablemente todavía estamos lejos de la implementación práctica de un desciframiento cuántico de los estándares del NIST, pero ignorar tales avances teóricos sería el colmo de la frivolidad.