Amenaza cuántica para la criptografía postcuántica: el algoritmo de AWS pone en duda la resistencia de los estándares basados en retículos
En el mundo de la criptografía se está gestando un cambio potencialmente tectónico. Mi análisis de un nuevo preprint presentado por el investigador de Amazon Web Services, Daniel Simon, ha revelado un algoritmo cuántico que podría acelerar radicalmente la resolución de problemas matemáticos que subyacen en la criptografía postcuántica. Esto no es solo una curiosidad teórica: es un desafío directo a las nociones establecidas sobre la seguridad de los estándares modernos.
La innovación clave de Simon radica en que su algoritmo demuestra una dependencia polinómica, y no exponencial, del tiempo de ejecución respecto al tamaño del problema. Si este resultado supera una verificación independiente, tendremos que reconsiderar el propio paradigma de la resistencia de los criptosistemas basados en retículas frente a la computación cuántica. Sin embargo, es importante subrayar: esto no es un ataque práctico contra los estándares vigentes, como ML-KEM o ML-DSA, sino más bien un avance teórico que señala posibles brechas.
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 problema de la clase lateral diedral (Dihedral Coset Problem, DCP). A primera vista, DCP no se utiliza directamente para proteger carteras o conexiones, pero es precisamente el eslabón que conecta con problemas más complejos de la criptografía de retículas. Ya a principios de la década de 2000, Oded Regev demostró que una solución eficiente de DCP abriría el camino para descifrar ciertas variantes de problemas en retículas multidimensionales, pero entonces se requería una herramienta idealizada inalcanzable.
Simon afirma haber sorteado esta limitación realizando la transformación necesaria directamente en una computadora cuántica. En combinación con trabajos anteriores, su algoritmo potencialmente se extiende a problemas clave como el Problema del Vector Más Corto (Shortest Vector Problem, SVP) y el Aprendizaje con Errores (Learning With Errors, LWE). Precisamente en la dificultad de estos problemas se basa la seguridad de los estándares del NIST adoptados en 2024, incluidos ML-KEM y ML-DSA. Si el algoritmo se confirma, demostraría que las computadoras cuánticas son teóricamente capaces de resolver estos problemas de manera mucho más eficiente de lo que se suponía anteriormente.
El pánico es prematuro, pero la vigilancia es obligatoria
No obstante, no recomendaría al mercado entrar en pánico. El trabajo de Simon no demuestra una forma de recuperar claves de ML-KEM ni de falsificar firmas de ML-DSA con parámetros reales. LWE es toda una familia de problemas, y los estándares prácticos utilizan sus variantes estructuradas, por lo que un resultado para una clase no se transfiere automáticamente a todos los sistemas. Además, el preprint carece de una estimación de los recursos necesarios —cúbits lógicos, compuertas y corrección de errores— para atacar tamaños criptográficamente significativos. La historia conoce ejemplos de afirmaciones ruidosas que se derrumbaron: en 2024, el investigador Yilei Chen ya anunciaba un algoritmo polinómico para LWE, pero su demostración contenía un error y retiró sus conclusiones.
Mi veredicto profesional: este preprint no es un motivo para una migración inmediata, pero sí una señal seria para la industria criptográfica. Estamos al borde de una era donde las investigaciones teóricas pueden transformarse rápidamente en amenazas reales. Los proyectos que dependen de la seguridad a largo plazo deberían incorporar ya en sus hojas de ruta la flexibilidad para transitar hacia nuevos primitivos criptográficos potencialmente más resistentes, en lugar de esperar a que la «fractura cuántica» se convierta en un hecho consumado.