¿Qué vendrá primero: la criptografía cuántica segura o una computadora cuántica lo suficientemente grande como para descifrar rápidamente las claves privadas?

Pregunta original: ¿Qué vendrá primero: la criptografía de seguridad cuántica, o una computadora cuántica lo suficientemente grande como para descifrar rápidamente las claves privadas?

La criptografía de seguridad cuántica llegará primero, o posiblemente ya exista.

Los algoritmos cuánticos más relevantes que rompen la criptografía son el algoritmo de Shor y el algoritmo de Grover.

1. La mayoría de los algoritmos criptográficos simétricos (AES) son vulnerables solo a Grover. Este algoritmo reduce aproximadamente la seguridad de AES-128 al equivalente de una clave de 64 bits (que se considera rota), y reduce la seguridad de AES-256 a 128 bits (que se considera segura).
   Por lo tanto, incluso con una computadora cuántica lo suficientemente grande, AES-256 es seguro en el futuro previsible. Algo similar se aplica a las funciones hash criptográficas.
2. Los algoritmos criptográficos asimétricos más comunes (RSA y ECC) son vulnerables a Shor. Cuando una computadora cuántica se vuelve lo suficientemente grande, esos algoritmos se rompen por completo y se vuelven inútiles.
   Pero: hay muchas alternativas que no parecen ser vulnerables a Shor. Ejemplos son la criptografía basada en código y la criptografía basada en red.
   La razón principal por la que estos no se usan comúnmente:

1. Son menos eficientes que RSA / ECC. ¿Por qué usar algo menos eficiente cuando la amenaza parece mayormente teórica?
2. Hay poco o ningún consenso sobre qué algoritmos usar y cómo. Los científicos todavía están tratando de mejorar sus esquemas antes de que cualquier esfuerzo de estandarización dé frutos.

Por supuesto, esto no tiene en cuenta ningún otro desarrollo nuevo, en el que los científicos encuentren formas completamente nuevas de romper los cifrados, opcionalmente utilizando una computadora cuántica.

Ya tenemos criptografía de seguridad cuántica, pero todavía no tenemos computadoras cuánticas lo suficientemente grandes como para descifrar claves privadas.

Algunos de los enfoques existentes para la criptografía cuántica resistente:

• Criptografía multivariante – Wikipedia
• Criptografía basada en hash – Wikipedia
• Criptografía basada en celosía: Wikipedia (mi favorito, tanto el sistema NTRU como la prueba de Craig Gentry de cifrado totalmente homomórfico se basan en esto)
• Intercambio de claves de isogenia supersingular – Wikipedia
• Criptografía basada en código, como códigos de corrección de errores: criptosistema Niederreiter – Wikipedia o criptosistema McEliece – Wikipedia

De hecho, a pesar de los titulares de “esta vez de verdad, muchachos” en el pasado sobre las computadoras cuánticas universales realmente existentes, no es seguro que podamos construir dicho dispositivo en el futuro previsible, ya que cada qbit adicional parece causar una magnitud de problemas más que la anterior.

Este artículo proporciona información sobre los desafíos de construir computadoras cuánticas más potentes: el problema con la computación cuántica

La criptografía de seguridad cuántica probablemente tendrá un uso generalizado mucho antes de que la verdadera supremacía cuántica esté disponible públicamente. Existen varios algoritmos de seguridad cuántica, y creo que el proyecto Tor ya ha incorporado algún esquema basado en la red en su capa de cifrado.

Los algoritmos de seguridad cuántica existentes son bastante complicados pero ciertamente posibles de implementar para alguien con habilidades de programación razonablemente avanzadas; Implementé NewHope yo mismo usando Python. La velocidad sigue siendo un problema, pero esto es una cuestión de refinamiento, no de avance.

La supremacía cuántica, la capacidad de ejecutar programas arbitrarios en una computadora cuántica, lo que rompe el RSA, por otro lado, no existe, y aunque los equipos de IBM y otras organizaciones pueden estar muy cerca, nadie sabe a ciencia cierta si es posible .

La criptografía de seguridad cuántica lo hará. Se llama criptografía post-cuántica y está (probablemente) aquí ahora. Lo digo probablemente porque el contendiente principal (basado en la red) aún no ha sido reclamado como demostrablemente seguro y los algoritmos que han demostrado ser seguros tienen tamaños de clave muy, muy largos, por lo que puede no ser práctico.

Pero, aún así, están años por delante de una computadora que puede romper el RSA.