Uno de los usos más consolidados y disruptivos de una futura computadora (u ordenador) cuántica(o) es la capacidad de romper 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: un ordenador cuántico lo suficientemente potente podría hacer que nuestros principales esquemas criptográficos pierdan su valor. Si bien los puzzles matemáticos que los sustentan son prácticamente irresolubles para la computación clásica, serían completamente solucionables para una computadora cuántica lo suficientemente grande. Esto es un problema porque estos esquemas proporcionan seguridad a 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 científico en computación Oded Regev, de la Universidad de Nueva York, ha descubierto un nuevo algoritmo que podría reducir sustancialmente el número de cúbits 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 con 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 recopilar 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.
Es probable que la espera sea bastante larga. La mayoría de las implementaciones de RSA se basan en claves de al menos 2.048 bits, lo que equivale a un número de 617 dígitos. Los investigadores de Fujitsu calcularon recientemente que una computadora cuántica completamente tolerante a fallos con 10.000 cúbits, requeriría 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 cúbits, 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². El enfoque de Regev solo requeriría n1,5 puertas porque busca factores primos realizando multiplicaciones más pequeñas de muchos números en lugar de multiplicaciones muy grandes de un sólo 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 2.048 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 rompan 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 cúbits 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á cúbits adicionales y consumirá cualquier ventaja computacional que tenga.
En cualquier caso, 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 están en constante movimiento, y el cambio a esquemas poscuánticos no puede ocurrir lo suficientemente rápido.