Las computadoras cuánticas podrían descifrar el cifrado antes de lo esperado con un nuevo algoritmo
Bruno I. Scollo
Uno de los usos más consolidados y disruptivos de una futura computadora cuántica es la capacidad de descifrar el cifrado. Un nuevo algoritmo podría reducir significativamente la barrera para lograrlo.
A pesar de todo el revuelo en torno a la computación cuántica, todavía existen importantes interrogantes sobre para qué serán realmente útiles las computadoras cuánticas. Hay esperanzas de que puedan acelerar todo, desde los procesos de optimización hasta el aprendizaje automático, pero en muchos casos no está claro hasta qué punto serán más fáciles y rápidos.
Sin embargo, una cosa es bastante segura: una computadora cuántica lo suficientemente potente podría hacer que nuestros principales esquemas criptográficos pierdan su valor. Si bien los acertijos matemáticos que los sustentan son prácticamente irresolubles para las computadoras clásicas, serían completamente solucionables para una computadora cuántica lo suficientemente grande. Esto es un problema porque estos esquemas aseguran la mayor parte de nuestra información en línea.
La salvación ha sido que los procesadores cuánticos actuales están muy lejos del tipo de escala requerido. Pero según un informe de Science, el informático Oded Regev de la Universidad de Nueva York ha descubierto un nuevo algoritmo que podría reducir sustancialmente el número de qubits necesarios.
Básicamente, el enfoque reelabora uno de los algoritmos cuánticos más exitosos hasta la fecha. En 1994, Peter Shor, del MIT, ideó una forma de determinar qué números primos deben multiplicarse para obtener un número concreto: un problema conocido como factorización prima.
Para grandes cantidades, este es un problema increíblemente difícil que rápidamente se vuelve intratable en las computadoras convencionales, razón por la cual se utilizó como base para el popular esquema de cifrado RSA. Pero al aprovechar fenómenos cuánticos como la superposición y el entrelazamiento, el algoritmo de Shor puede resolver estos problemas incluso para números increíblemente grandes.
Ese hecho ha provocado no poca cantidad de pánico entre los expertos en seguridad, sobre todo porque los piratas informáticos y los espías pueden aspirar datos cifrados hoy en día y luego simplemente esperar a que se desarrollen computadoras cuánticas lo suficientemente potentes para descifrarlos. Y aunque se han desarrollado estándares de cifrado poscuánticos, implementarlos en la web podría llevar muchos años.
Aunque es probable que la espera sea bastante larga. La mayoría de las implementaciones de RSA se basan en claves de al menos 2048 bits, lo que equivale a un número de 617 dígitos. Los investigadores de Fujitsu calcularon recientemente que se necesitaría una computadora cuántica completamente tolerante a fallas con 10.000 qubits durante 104 días para descifrar un número tan grande.
Sin embargo, el nuevo algoritmo de Regev, descrito en una preimpresión publicada en arXiv, podría reducir sustancialmente esos requisitos. Básicamente, Regev ha reelaborado el algoritmo de Shor de modo que sea posible encontrar los factores primos de un número utilizando muchos menos pasos lógicos. Realizar operaciones en una computadora cuántica implica crear pequeños circuitos a partir de unos pocos qubits, conocidos como puertas, que realizan operaciones lógicas simples.
En el algoritmo original de Shor, el número de puertas necesarias para factorizar un número es el cuadrado del número de bits utilizados para representarlo, que se denota como n 2 . El enfoque de Regev sólo requeriría n 1,5 puertas porque busca factores primos realizando multiplicaciones más pequeñas de muchos números en lugar de multiplicaciones muy grandes de un solo número. También reduce la cantidad de puertas requeridas mediante el uso de un algoritmo clásico para procesar aún más las salidas.
En el artículo, Regev estima que para un número de 2048 bits esto podría reducir el número de puertas necesarias en dos o tres órdenes de magnitud. De ser cierto, eso podría permitir que computadoras cuánticas mucho más pequeñas descifren el cifrado RSA.
Sin embargo, existen limitaciones prácticas. Para empezar, Regev señala que el algoritmo de Shor se beneficia de una serie de optimizaciones desarrolladas a lo largo de los años que reducen la cantidad de qubits necesarios para ejecutarlo. Aún no está claro si estas optimizaciones funcionarían en el nuevo enfoque.
Martin Ekerå, investigador de computación cuántica del gobierno sueco, también dijo a Science que el algoritmo de Regev parece necesitar memoria cuántica para almacenar valores intermedios. Proporcionar esa memoria requerirá qubits adicionales y consumirá cualquier ventaja computacional que tenga.
No obstante, la nueva investigación es un recordatorio oportuno de que, cuando se trata de la amenaza de la computación cuántica al cifrado, los objetivos se mueven constantemente, y el cambio a esquemas poscuánticos no puede ocurrir lo suficientemente rápido.
Fuente: https://singularityhub.com/2023/10/02/quantum-computers-could-crack-encryption-sooner-than-expected-with-new-algorithm/
