Sigue El lado del mal en Telegram
Chema Alonso en Threads
Chema Alonso en Mastodon
Chema Alonso en BSKY
Chema Alonso en Linkedin
DragonJAR
8.8 Chile
Ekoparty
e-Hack MX 
AREA 51 
Comunidad Dojo Panamá 
ARPAHE SOLUTIONS 
El algoritmo que amenazó a 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 )
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.
Figura 3: Problema de Simon
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.
Figura 4: Algoritmo de Shor en Wikipedia en Español.
Causante de que el RSA sea inseguro con la llegada de los ordenadores cuánticos
Causante de que el RSA sea inseguro con la llegada de los ordenadores cuánticos
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.
Nuestro nuevo libro en 0xWord escrito por: Chema Alonso,
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.
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.
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.
Figura 7: El mismo retículo con dos bases distintas: la ”buena” (vectores
cortos y casi
perpendiculares) y la ”mala” (largos y casi paralelos).
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.
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.
Figura 8: On Lattices, Learning with Errors,
¿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.
Figura 10: A subexponential-time quantum algorithm for
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
Lo que decía el paper: quitar el andamio sin tirar el edificio.
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.
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.
Figura 13: Foro Público de Quantum Security de
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:
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:
Un ordenador cuántico podría atacar de forma eficiente el problema que sostiene buena parte de la criptografía postcuántica.
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.
1. Aproximado no es exacto: El resultado no encontraba el vector más corto, sino uno razonablemente corto. De ahí a ”te recupero esta clave de ML-KEM” hay un trecho considerable.
2. Peor caso frente a caso medio, y una capa más: Los problemas de retículos que aparecen en las reducciones son de peor caso; los que protegen vuestro navegador son instancias medias con parámetros muy concretos. Y hay un salto adicional: ML-KEM y ML-DSA no descansan sobre LWE a secas, sino sobre Module-LWE, que arrastra estructura algebraica extra.
3. Polinómico no significa práctico: El propio análisis del paper exige una constante c ≥12, lo que se traduce en del orden de n13 muestras. Comparadlo con el coste cúbico del algoritmo de Shor. Un polinomio de grado trece es polinómico igual que ir andando a la Luna es una distancia finita.
4. No había estimación de recursos: Ni qubits lógicos, ni puertas, ni profundidad de circuito, ni operaciones corregidas de errores. Nada.
5. Era un preprint: Sin revisión por pares, con el propio autor calificándolo de preliminar en el título, con cuatro de sus lemas presentados explícitamente como esbozos ”Proof. (Sketch)”.
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.
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.
Otros artículos sobre Quantum Computing publicados:
- III edición del Programa de Especialización de Quantum y Post-Quantum Computing para Ciberseguridad: Noviembre 2026
- Libro de Quatum Security: Tecnología Cuántica & Ciberseguridad. Criptográfica Cuántica y Post-Cuántica.
- Foro Público de Quantum Security de la Universidad de Deusto en MyPublicInbox
- Quantum Computing Cybersecurity Preparedness Act: Comienza la era de Ciberseguridad Post-Quantum en Estados Unidos
- Hamming Quasi-Cyclic (HQC-KEM): Nuevo Key-Encapsulation Mechanism en Post-Quantum Cryptography
- FrodoKEM: Un Key-Encapsulation Mechanism Quantum-Safe (PQC) que recibe su nombre por "El señor de los Anillos"
- La Gran Búsqueda de Números Primos de Mersenne en Internet para superar el mayor Número Primo conocido hasta la fecha
- Cómo acelerar los algoritmos de Inteligencia Artificial con Computadores Analógicos Ópticos (AOC)
- Premio Nobel en Física 2025: El trabajo del "Efecto Tunel" que trajo la cuántica a nuestro mundo y abrió la puerta a los ordenadores cuánticos
- Un Reloj Atómico Óptico del MIT con Optimización Cuántica para medir el Tiempo del Futuro
- Quantum Cryptography: Una comunicación con cifrado cuántico
- Factorización de RSA con un Optimizador de Quantum Computing (y Classic Computing)
- Cuánto del tráfico en Internet funciona con Post-Quantum Cryptography
- Algoritmo Cuántico de Grover: Un algoritmo de búsqueda optimizado por superposición cuántica
- Quantum Sensors: Cuando lo invisible se hace visible gracias al Mundo Cuántico
- Bitcoin vs Quantum Computers: Hora de pasar a Post-Quantum Cryptography
- El White Paper de MasterCard que urge a pasar a Quantum Safe: Post-Quantum Cryptography (PQC) & Quantum Key Distribution (QKD)
- Dyber: Hardware-Accelerated Post-Quantum Cryptography (PQC)
- Cómo ser Quantum Safe y desplegar Post-Quantum Cryptography (PQC) con Cloudflare
- Quantum GPS: Navegación con GPS cuánticos para evitar ataques de Jamming & Spoofing
- Cómo comprobar si un Web Site es Quantum Ready con Post-Quantum Cryptography usando Radar
- Alaniz Cipher: Un Cifrado Simétrico Quantum Resistant
- Los Papers Académicos de los algoritmos PQC de Autenticación y Firma Digital en la Ronda 3 del NIST
- Blind Quantum Computing (1) (2) (3) (4)
- Computación Cuántica y Fusión Nuclear: La Receta para fabricar un "Sol en la Tierra"
- Claude Mythos Preview debilita los algoritmos criptográficos PQC HAWK y AES con nuevos ataques
No hay comentarios:
Publicar un comentario