sábado, agosto 22, 2026

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.

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

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.

Figura 2: Los nueve días, de un vistazo. Del envío del preprint
al resultado de imposibilidad verificado por máquina

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.

Figura 4: El Lema 3 del manuscrito de Simon, uno de los cuatro
resultados cuya demostración aparece marcada como ”(Sketch)”.
Fijaos en las dos palabras que siguen a ”Proof ”

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.

Figura 5: A Polynomial-Time QuantumAlgorithm for the Dihedral Coset Problem

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: 

”We are showing directly that the algorithm cannot possibly work”. 

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.

Figura 7: La idea del argumento. Mientras el algoritmo conserva
las etiquetas de Fourier, las ramas de la superposición mantienen
una relación de fase definida y el secreto es recuperable. Al
descartarlas, esa relación se pierde y con ella toda la información

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.

Figura 8: Foro Público de Quantum Security de
la Universidad de Deusto en MyPublicInbox

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.

Figura 9: Lo que el paper prometía frente a lo que la refutación demuestra.
Un algoritmo cuyo coste crece como 2n/9 no es un algoritmo eficiente
en ningún sentido útil de la palabra

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.

Figura 10: Los agradecimientos de la nota que refuta el algoritmo.
El segundo nombre de la lista es el del autor del algoritmo refutado.

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.

Figura 11: El repositorio con la formalización en Lean 4
de la refutación, publicado junto con la nota.

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:

Figura 12: La declaración sobre uso de inteligencia artificial que acompaña
a la refutación. La versión general del teorema salió de una conversación
con modelos de lenguaje, y la formalización en Lean 4 también.

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.

Estaba ayudando a demostrar que la grieta no existía. Ideas propuestas con ayuda de una máquina, verificadas por otra máquina, publicadas en abierto y todo ello en menos de dos semanas. Hace diez años esto habrían sido meses de correos cruzados entre departamentos de medio mundo. Si alguien os pregunta alguna vez para qué sirven los asistentes de demostración formal, este es el ejemplo que hay que dar.

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.


Figura 13: Quantum y Post-Quantum Computing para Ciberseguridad.
Formación Especializada, Libro & Foro Online

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. 


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? 


Otros artículos sobre Quantum Computing publicados:

Publicado por Chema Alonso a las 6:01 a. m. 0 comentarios

Etiquetas: , , , , ,

Suscribirse a: Entradas (Atom)

Entrada destacada

Hacking IA: Jailbreak, Prompt Injection, Hallucinations & Unalignment. Nuestro nuevo libro en 0xWord

Pocas veces me ha hecho tanta ilusión que saliera un nuevo libro en 0xWord como con este libro de " Hacking IA: Jailbreak, Prompt Inje...

Entradas populares