El algoritmo que amenazó la Criptografía Post-Cuántica

Hace poco os contaba en este blog cómo una inteligencia artificial se había sentado, por
primera vez y por derecho propio, en la mesa de los criptoanalistas en el artículo de «Claude Mythos Preview debilita los algoritmos criptográficos PQC HAWK y AES con nuevos ataques«. Terminaba aquel
artículo con una pregunta que entonces me pareció puramente retórica sobre si ¿estarán nuestros candados preparados para un mundo donde las máquinas buscan las grietas?

No han sido las máquinas, pero la pregunta resultó tener una fecha de caducidad muy corta en forma de respuesta aviso. El susto llegó a principios de
agosto de 2026, y de la mano de alguien a quien nadie en este campo puede tomarse a la
ligera. Esta historia os la voy a contar en os partes,

La primera mitad de la historia, ésta, donde os voy a contar qué se anunció exactamente, por qué era tan serio y
por qué, aun así, ninguna persona sensata salió corriendo a apagar los servidores. La segunda
mitad de la historia, será sobre cómo la comunidad lo desmontó en nueve días, y con una ayuda bastante inesperada, y os la contaré en el próximo artículo.

El hombre que ya rompió la criptografía una vez

El autor del preprint no es un aficionado que ha leído tres entradas de la Wikipedia. Es
Daniel R. Simon, del grupo de Criptografía de Amazon Web Services, y su apellido os
resultará familiar si habéis pasado por cualquier curso de computación cuántica: en 1994
publicó el algoritmo de Simon, uno de los primeros resultados que demostró de forma limpia
una separación exponencial entre lo que puede hacer un ordenador clásico y lo que puede
hacer uno cuántico.

Aquel resultado no rompía nada por sí solo, porque el problema que resolvía era artificial,
inventado a propósito para el argumento. Pero fue la chispa: Peter Shor lo leyó, entendió la
maquinaria que había debajo y ese mismo año publicó su algoritmo, el que factoriza números
grandes en tiempo polinómico y el que hará saltar por los aires RSA y la Criptografía de Curva Elíptica en cuanto tengamos la máquina cuántica.

Tenemos, por tanto, a la persona que inspiró el algoritmo destinado a acabar con la
criptografía actual regresando treinta y dos años después, esta vez sobre el sustituto. La
simetría es demasiado buena para ser casualidad, y explica en buena medida por qué nadie
se tomó este preprint a la ligera.

Un repaso rápido: por qué lo hemos apostado casi todo a una rejilla
(los algoritmos lattice-based )

Los dos algoritmos de propósito general que el mundo entero está desplegando ahora mismo,
ML-KEM (antes Kyber) y ML-DSA (antes Dilithium), pertenecen a la misma familia: los
retículos. No es que el NIST no tuviera otras cartas —SLH-DSA, el antiguo SPHINCS+,
se apoya solo en funciones hash y no toca un retículo ni de lejos—, pero el peso real de
la migración recae sobre esos ML-KEM y ML.DSA. Y el tercer algoritmo que viene en camino, FN-DSA (el antiguo
Falcon), también está basado e retículos, aunque de un tipo distinto.

También es importante citar en esta parte de la historia a Frodo-KEM, que para librarse del «anillo» de los retículos por si algún día aparecía una debilidad matemática en ellos, hubiera otra alternativa. Por eso le llamaron Frodo, en honor a «Lord of the Ring«, que es el hobbit más famoso de la historia luchando por librarse de un anillo.

Un retículo es, en el fondo, una rejilla de puntos. Pensad en el papel milimetrado, pero en mil
dimensiones y torcido, definido por una base de vectores que no son perpendiculares entre sí
ni miden lo mismo. Sobre esa rejilla se plantean los dos problemas de siempre. 

El SVP pide encontrar el punto
más cercano al origen sin ser el origen: en dos dimensiones lo resolvéis mirando el dibujo, en
mil y con una base torcida es una pesadilla. Y el LWE os entrega un puñado de ecuaciones
lineales cuya solución es la clave secreta, pero con un ruido pequeño sumado a cada una: sin
ruido lo resuelve un estudiante de primero con Gauss, con ruido se convierte en una sopa de
letras.

La gracia de estos problemas es que generarlos resulta trivial, resolverlos parece imposible y,
sobre todo, que nadie conocía un atajo cuántico. Shor destroza la factorización porque
esta esconde una estructura periódica muy concreta que la transformada cuántica de Fourier
detecta a la primera. Los retículos, en principio, no tienen esa estructura tan amable.

Es la intuición clásica de por qué un
retículo puede esconder un secreto, aunque conviene no tomarla al pie de la letra: la clave
pública de ML-KEM no es literalmente una base mala, sino un sistema de ecuaciones con
ruido

La puerta que Regev dejó construida en 2004

Aquí entra el protagonista técnico de la historia, con un nombre diseñado para espantar
lectores: el Problema del Coset Diedral, o DCP por sus siglas en inglés. Conviene
traducirlo.

Existe una familia enorme de problemas llamada problema del subgrupo oculto, y resulta que
casi todos los grandes éxitos de la computación cuántica son casos particulares de ella. El
algoritmo de Shor es un problema de subgrupo oculto sobre un Grupo Abeliano, es decir,
conmutativo, de los ”fáciles”. El de Simon de 1994, también. Los ordenadores cuánticos son
extraordinariamente eficaces en ese terreno, porque la transformada de Fourier diagonaliza
esos grupos y la interferencia se encarga del resto.

El grupo diedral (el de las simetrías de un polígono: rotaciones y reflexiones) no conmuta.
Girar y luego reflejar no es lo mismo que reflejar y luego girar, y ahí es donde el método se
atasca. En su versión de Coset, el problema queda planteado así: recibes muchísimos estados
cuánticos, cada uno de ellos una superposición de | 0, x ⟩ y | 1, x + s ⟩, con x distinto en cada
muestra y s un valor secreto que se repite en todas. Tu misión, si decides aceptarla, es
recuperar s.

¿Y qué tiene esto que ver con los retículos?  En 2004, Oded Regev demostró una reducción: quien supiera resolver el DCP de forma eficiente, sabría resolver ciertos problemas difíciles
de retículos. Esa reducción es incondicional, no depende de ninguna suposición extra, y
en 2018 Brakerski, Kirshanova, Stehlé y Wen la afinaron todavía más, conectando el LWE
con una variante extrapolada del mismo problema diedral [8]. La puerta llevaba veinte años
construida y señalizada.

Lo que faltaba era la llave: un algoritmo eficiente para el DCP. Y aquí es donde
aparece el famoso oráculo, que conviene situar bien porque medio Internet lo colocó en
el sitio equivocado. En un trabajo distinto del anterior, el propio Regev dio también un
procedimiento en tiempo polinómico para resolver el DCP, pero suponiendo acceso a un
oráculo de suma de subconjuntos: una cajita mágica capaz de resolver otro problema
difícil que nadie sabe resolver. Es como decir que sabes llegar a Marte suponiendo que alguien
te presta una nave que llega a Marte.

Fijaos bien en dónde queda el hueco, porque es la clave de todo: el tramo que va del
DCP hasta los retículos está entero. Lo que nadie tenía era la primera pieza, un algoritmo
real para el DCP. Y el mejor conocido, el de Greg Kuperberg (2005), corría en tiempo
subexponencial: mucho mejor que la fuerza bruta, pero muy lejos de polinómico.

El tramo que va del DCP
hasta ML-KEM y ML-DSA está completo y demostrado; la pieza que faltaba estaba justo
antes, un algoritmo eficiente para el DCP que no dependiese de un oráculo 

El 3 de agosto Simon subió a ePrint un manuscrito titulado «A Polynomial-Time QuantumAlgorithm for the Dihedral Coset Problem«. La IACR lo aprobó y lo publicó el día 6 de Agosto, que
es cuando la prensa especializada se hizo eco, y el paper fue revisado el día 11 de Agosto. Lo que afirmaba era exactamente la llave que
faltaba: resolver el DCP en tiempo polinómico sin necesidad del oráculo.

La dificultad que hay que salvar es más sutil de lo que parece, y merece la pena entenderla
bien, porque va a ser la clave de todo lo que os cuente en el próximo artículo. 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. Y a lo largo del 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í. El problema es que, 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.

La propuesta de Simon consistía en dividir las muestras en bloques y procesarlos de forma
que unos quedasen limpios de fases indeseadas mientras los demás se apartaban dejando el
estado casi equilibrado. Después se transfiere a un qubit de repuesto la fase que codifica un
bit del secreto y se repite el proceso de manera recursiva.

El artículo subrayaba además un detalle: el algoritmo afirmaba tolerar muestras defectuosas
hasta una tasa de 1/O(log n). La idea es que las reducciones que van desde los retículos hasta
el DCP pueden introducir ese tipo de basura, y el algoritmo de Kuperberg exige muestras
limpias.

Conviene decir, eso sí, que este punto fue discutido de inmediato: Elena Kirshanova,
coautora del trabajo de 2018 sobre el que se apoya toda la reducción, señaló que la tolerancia
al ruido no llega a usarse en ningún momento del paper, porque las reducciones existentes
ya entregan muestras limpias en cantidad polinómica. Y la razón de fondo por la que el
algoritmo de Kuperberg nunca inquietó a nadie es más simple: es subexponencial, y punto.

Con oráculo o sin él, el corolario final afirmaba resolver en tiempo polinómico aproximaciones
al SVP con factor √n polylog(n) e instancias de LWE en el régimen equivalente. Traducido:

Y aquí un detalle que parece menor y que va a resultar decisivo en el próximo artículo:
ese corolario final, el que fija los parámetros concretos de SVP y LWE, no venía derivado
en el manuscrito, sino atribuido a comunicaciones personales con Daniele Micciancio y
Seyoon Ragavan. Guardad ese segundo nombre.

Por qué nadie salió corriendo a apagar los servidores

Y sin embargo la reacción de la comunidad no fue el pánico, sino una mezcla muy saludable
de ”esto es enorme” y ”conviene mantener la calma”. Merece la pena entender por qué, porque
aquí hay una lección práctica sobre cómo leer titulares tecnológicos.

Al segundo punto, eso sí, le habían quitado bastante fuelle apenas unos días antes, y
esto casi nadie lo contó. Weiqiang Wen y Jinwei Zheng, de Télécom Paris, publicaron un trabajo ya revisado por pares y aceptado en CRYPTO 2026 en el que demuestran unaequivalencia cuántica en tiempo polinómico entre Module-LWE y una variante estructuradadel problema diedral extrapolado. 

Wen es coautor del artículo de 2018 sobre el que se
apoya la reducción de Simon, así que no hablamos de dos grupos que llegan por casualidad al
mismo sitio, sino de la misma línea de investigación avanzando. El puente hasta el supuesto
de dificultad que hay debajo de ML-KEM era, de repente, más corto de lo que parecía la
semana anterior.

Quien sí quedaba fuera de esta vía concreta es FN-DSA (el antiguo Falcon), que se apoya
en retículos NTRU y para el que no se conoce ninguna reducción publicada que lo conecte
con el DCP.
Si el resultado hubiera sido correcto, habría supuesto un avance mayúsculo de complejidad
teórica y un aviso muy serio sobre los cimientos. Pero no era un ataque: nadie tenía motivos
para detener su migración a ML-KEM, y a día de hoy sigue sin haberlos.

Y entonces la comunidad se puso a leer

Un preprint de este calado no se queda quieto mucho tiempo. El fin de semana siguiente a
su publicación, criptógrafos de primer nivel ya tenían el manuscrito abierto y el lápiz en la
mano, y para el 15 de agosto el asunto estaba cerrado.

Lo interesante no es que encontraran un error. Es que hicieron algo bastante más definitivo,
y lo hicieron con una herramienta que hasta hace muy poco no habría estado sobre la mesa.
Pero eso, junto con la respuesta a la pregunta con la que abría este artículo, os lo cuento en
el próximo.