Cómo se desmontó el algoritmo que amenazaba a la Criptografía Post Cuántica 9 días después

En el artículo anterior os contaba que el 6 de agosto de 2026 apareció en el archivo ePrint
de la IACR un manuscrito de Daniel R. Simon, del grupo de Criptografía de AmazonWeb Services, que afirmaba haber resuelto en tiempo polinómico el Problema del CosetDiedral. Si aquello era cierto, por una reducción que Oded Regev demostró en 2004 caía en cascada la seguridad teórica de toda la familia de los retículos, y con ella la de
ML-KEM y ML-DSA, es decir, la de los dos algoritmos que el mundo entero está desplegando
ahora mismo para sobrevivir a la llegada de los ordenadores cuánticos.

Aquel artículo lo cerré en el peor momento posible: con el manuscrito recién colgado, la
comunidad criptográfica abriéndolo en fin de semana y nadie en condiciones de decir todavía
si aquello se sostenía o no. Lo que ocurrió a partir de ahí es, en mi opinión, bastante más
interesante que el propio anuncio.

Así que os ahorro la intriga, porque el final no es lo importante: el trabajo no era correcto.
Lo que merece la pena contar es cómo se demostró que lo era, en cuánto tiempo y con
qué herramientas. Desde que el manuscrito se hizo público hasta que quedó formalmente
descartado pasaron nueve días. Nueve. Sin comités, sin revisión por pares a seis meses vista
y con todo el proceso a la vista de cualquiera que quisiera mirar.

Un recordatorio de treinta segundos: dónde estaba la dificultad

Para que lo que viene se entienda, hay que tener presente una sola idea del artículo anterior.
En un algoritmo cuántico la respuesta casi nunca está guardada en un sitio concreto: está
repartida en las fases relativas entre todas las ramas de la superposición. Es una propiedad
del conjunto, no de ninguna pieza suelta.

Durante el cálculo se van acumulando restos, información residual enganchada al estado
que hay que borrar para que las amplitudes puedan volver a interferir entre sí. Y ahí
está el problema: si borráis esa basura midiéndola, os lleváis la fase por delante. Es como
intentar desmontar el andamio de un edificio sin tocar el edificio. Regev resolvía esa papeleta
suponiendo un oráculo de suma de subconjuntos, una caja negra que nadie sabe
construir. La aportación de Simon consistía, precisamente, en prescindir de ella. 

Retened la palabra andamio. Va a volver.

El fin de semana siguiente: la comunidad se pone a leer

Aquí es donde el episodio resulta más revelador, porque enseña cómo funciona de verdad la
ciencia cuando nadie la está mirando desde fuera.

El manuscrito se hizo público un jueves. El fin de semana siguiente ya había criptógrafos
leyéndolo con el lápiz en la mano y comentando en abierto lo que iban encontrando, y la
discusión se concentró enseguida en unos pocos resultados intermedios del artículo, muy enparticular en el Lema 3. 

No voy a poner aquí frases entrecomilladas ni a atribuir juicios
técnicos concretos a nadie, porque buena parte de aquella conversación ocurrió en canales
y foros que no dejan un enlace estable al que poder apuntaros, y prefiero no atribuir a un
investigador una frase que no pueda enseñaros. Lo que sí podéis comprobar vosotros mismos, y no depende de que nadie os lo cuente, es lo
que trae el propio manuscrito.

Cuatro de los resultados que sostienen el teorema principal llevan sus demostraciones
marcadas como ”(Sketch)”: el Lema 1 en la página 7, el Lema 3 en la 11, el corolario del Lema
3 en la 12 y el Lema 4 en la 13. El único de los lemas centrales que viene con demostración
completa es el Lema 2. Dicho de otro modo: en un paper que reclama tumbar los cimientos
de la Criptografía Post-Cuántica mundial, ninguna de las piezas críticas venía demostrada del
todo. El 11 de agosto Simon subió una versión revisada del manuscrito, y esa es la que hoy
encontraréis en ePrint. Cuatro días después llegó el golpe definitivo.

Fijaos en un detalle que se pierde con facilidad: aquí hay dos modos de refutación
encadenados, y son cualitativamente distintos. Primero, la comunidad encuentra errores en
las demostraciones, que en principio son reparables. Después, tres investigadores demuestran
algo mucho más fuerte. Ver las dos cosas ocurrir en menos de una semana, en abierto y a
la vista de todos, es una lección de método científico que difícilmente encontraréis mejor
contada en un libro de texto.

Día 15: no encontraron el error, demostraron que no hay arreglo

El 15 de agosto, Aparna Gupte (MIT), Seyoon Ragavan (Google Quantum AI y MIT)
y Mark Zhandry (Google Quantum AI y Stanford) publicaron una nota demoledora.
Y conviene fijarse bien en el matiz, porque es lo más importante de todo el artículo:
No encontraron un error en la demostración. Demostraron que el algoritmo no
puede funcionar.

La diferencia es abismal: un fallo en una demostración se parchea, pero un resultado de
imposibilidad no deja nada que parchear. Lo dicen ellos mismos en el abstract, sin rodeos: 

No están hablando del
análisis que Simon hace de su algoritmo, están mostrando directamente que el algoritmo no
puede funcionar. 

¿Y cuál es el argumento? Volvamos al andamio.

Durante el proceso, el algoritmo genera unas etiquetas clásicas al aplicar la Transformada
de Fourier, y las utiliza por última vez en el tercer paso del procedimiento, únicamente
para calcular unos pocos bits altos de cada bloque. A partir de ahí no vuelven a aparecer.

Los autores demuestran que, en consecuencia, todo el estado del algoritmo se puede
reconstruir con un error minúsculo, del orden de poly(n) 2−n/3, empleando solo el tercio
más significativo de esas etiquetas. Dos tercios de la información se descartan por el
camino. Y aquí está la clave: esas etiquetas eran precisamente lo que mantenía la coherencia entre
las distintas ramas de la superposición, y en esa coherencia era donde vivía el secreto. El
andamio era el edificio.

El teorema que demuestran es además más general que el algoritmo de Simon: cualquier
procedimiento que siga la plantilla de Regev y descarte suficiente información sobre esas
etiquetas resulta incapaz de distinguir el último bit del secreto con ventaja apreciable, por
sofisticado que sea el post-procesado posterior. No es que Simon lo hiciera mal: es que por
ese camino no se puede pasar. Si habéis estudiado algo de física, el argumento os resultará
familiar, porque es del mismo tipo que un límite fundamental de medida. Si la información
ya no está en el sistema, no hay procesado que la recupere.

Lo que el paper enuncia formalmente es una disyuntiva: o el algoritmo tarda del orden de
2n/9 en promedio para al menos uno de los dos secretos, o su ventaja al distinguirlos es a
lo sumo poly(n) 2−n/9. Las dos cosas a la vez no pueden ser. Bernstein comprimió despuésesa disyuntiva en una sola cifra en su microblog: el cociente entre coste y probabilidad de
éxito del algoritmo sería de al menos 2n/9. Exponencial, no polinómico.

Los autores son además escrupulosamente honestos: dicen que no conocen ninguna vía de
reparación que esquive su teorema de forma significativa, pero se abstienen de afirmar que
no exista. Y dejan una moraleja constructiva para quien quiera seguir intentándolo, que
cualquier algoritmo para el DCP que siga la plantilla de Regev tendrá probablemente que
usar las etiquetas de Fourier casi enteras durante la fase de descomputación.

Y hay un último detalle que dice mucho de cómo funciona esta comunidad: en los
agradecimientos de la refutación, los tres autores dan las gracias, entre otros, al propio
Daniel R. Simon. No hay aquí ningún ánimo de humillar a nadie.

El detalle friki: la refutación viene con código (y con IA)

Llegamos ahora a la parte que a mí me parece la más significativa de todo el episodio, aunque
no salga en los titulares. Gupte, Ragavan y Zhandry no se limitaron a publicar un PDF con su argumento. Publicaron
también un repositorio con una especificación en Lean 4 del algoritmo de Simon y las
demostraciones verificadas por máquina tanto del teorema principal como del corolario
de imposibilidad. Cualquiera puede descargarlo, compilarlo y comprobar que el argumento cierra sin tener que fiarse de la buena fe de nadie.

Y no es una formalización de escaparate. En los 83 ficheros .lean del repositorio no aparece ni
un solo sorry —la palabra con la que Lean marca un hueco que aún hay que demostrar— ni
un solo axioma propio: cero objetivos sin resolver y cero atajos. Lo he comprobado clonando
el repositorio y pasando el rastreo que los propios autores documentan en su README,
que busca sorry, admit, axiom y compañía y debe salir vacío. Sale vacío. El mismo fichero
añade una auditoría de axiomas del núcleo sobre los tres teoremas principales, cuyo resultado
solo puede contener los principios lógicos estándar que Lean y Mathlib arrastran de serie
—propext, Classical.choice y Quot.sound—, nunca uno inventado para la ocasión.

Y aquí se cierra el círculo con el que abría el primer artículo. En la declaración sobre uso de
inteligencia artificial que incluyen en su nota, los autores cuentan que la versión general de
su teorema(la que convierte una refutación puntual en un resultado de imposibilidad amplio)
la encontraron conversando con modelos de lenguaje, y que emplearon esos mismos
modelos para producir la formalización en Lean, asumiendo ellos toda la responsabilidad
sobre la corrección del resultado. El propio README del repositorio lo repite en una sola
línea: la formalización se preparó con ayuda de un modelo. No es una interpretación mía. Lo dicen ellos, con nombres y apellidos, en un párrafo del
propio paper:

Merece la pena detenerse un momento en esto. Hace unas semanas os contaba en el en el artículo de «Claude Mythos Preview debilita los algoritmos criptográficos PQC HAWK y AES con nuevos ataques» que la IA había encontrado grietas reales en algoritmos criptográficos, y yo
terminaba aquel artículo preguntándome qué pasaría el día que apareciese una grieta en un
candado de verdad. Pues bien: la grieta llegó, y la IA no estaba en el bando
que yo esperaba.

Entonces, ¿hay que preocuparse?

La respuesta corta es que no. Los supuestos de dificultad sobre los que descansan ML-KEM
y ML-DSA están exactamente donde estaban el 2 de agosto: ningún algoritmo estandarizado
roto, ningún ataque calculado contra ningún conjunto de parámetros y ningún despliegue
que haya que pausar.

La respuesta larga es más incómoda, y es la que de verdad deberíamos llevarnos a casa.
Durante nueve días, mucha gente responsable de infraestructura crítica descubrió que su
plan de migración postcuántica dependía por completo de una única rama de las
matemáticas. Que el susto fuera falso no cambia el hecho de que era estructuralmente
posible, y la puerta que Regev construyó en 2004 sigue ahí, abierta y señalizada. Que este
intento de cruzarla haya fracasado no dice nada sobre el siguiente.

Por eso conviene fijarse en quién estaba mejor preparado. El BSI alemán lleva añosempujando la hibridación como norma —su posición es que la criptografía postcuántica
se despliegue siempre junto a RSA o Curva Elíptica, no en solitario— y mantiene en su guía
técnica esquemas ajenos a los retículos estructurados, como Classic McEliece, basado en
códigos. 

La ANSSI francesa va en la misma línea y considera la hibridación obligatoriadurante las dos primeras fases de la transición . Y el propio NIST construyó a concienciauna tubería de respaldo: seleccionó HQC en marzo de 2025 como alternativa basada encódigos frente a ML-KEM, y en mayo de 2026 hizo avanzar a tercera ronda a nuevecandidatos adicionales de firma. Ese último dato merece leerse despacio, porque es más elocuente de lo que parece.

De esos nueve, ocho no están basados en retículos. Hay isogenias (SQIsign),MPC-in-the-Head (MQOM, SDitH), multivariantes (UOV, MAYO, QR-UOV, SNOVA) yesquemas simétricos (FAEST). El único de la familia de los retículos era HAWK, y ya nisiquiera sigue en pie: su equipo lo retiró de la competición este mismo verano, después deque Mythos le encontrara una simetría oculta —un automorfismo no trivial
en el retículo— que rebaja el coste de recuperar una clave de HAWK-256 de 2 elevado a 64 a 2 elevado a 38 y
obliga a doblar el tamaño de clave para mantener el nivel de seguridad prometido. Si entráis hoy en la página del NIST, HAWK figura expresamente como retirado.

Dicho de otro modo: la tercera ronda de firmas adicionales del NIST es, a día de hoy, una
ronda enteramente ajena a los retículos. La red de seguridad existe y está tejida a propósito,
y el último hilo que quedaba de la familia sospechosa se soltó él solo apenas unas semanas
antes de que Simon subiera nada a ePrint. Nadie podrá decir que no lo habían pensado. La
pregunta abierta, y no es retórica, es si esa tubería se movería lo bastante rápido el día que
la contingencia sea de verdad.

Conclusión

Este episodio no ha demostrado que la criptografía de retículos sea frágil. Ha demostrado algo
mucho más valioso: que la comunidad que la vigila es rapidísima, transparente y capaz de
autocorregirse en cuestión de días. Un investigador de primer nivel lanzó una piedra enorme
al estanque, la comunidad se puso a leer el fin de semana, tres investigadores demostraron
con ayuda de una máquina que la piedra no llegaba al fondo, publicaron la prueba en abierto
para que cualquiera pueda compilarla, y le dieron las gracias al que la había tirado. 

Eso es
exactamente lo que uno espera de quienes custodian los cimientos matemáticos de Internet.
La próxima vez, sin embargo, puede que la piedra sí llegue al fondo.Y entonces la pregunta
ya no será si nuestros retículos aguantan, sino si tuvimos la prudencia de no apostarlo todo
a una sola rejilla. Porque construir el futuro de la criptografía sobre un único pilar, por muy
bien pintado que esté, sigue siendo construir sobre un único pilar. ¿Y si el próximo que venga
a ponerlo a prueba no se equivoca?