Computadoras cuánticas ¿El fin de la criptografía?

La computación cuántica es una de esas tecnologías que es tan misteriosa que el nombre de los personajes de TV la deja caer cuando quieren sonar inteligentes.

La computación cuántica como idea ha existido por un tiempo: la posibilidad teórica fue introducida originalmente por Yuri Manin y Richard Feynman en 1982. Sin embargo, en los últimos años, el campo se ha estado acercando preocupantemente a la practicidad..

Empresas como Google y Microsoft, así como agencias gubernamentales como la NSA, han estado buscando fervientemente computadoras cuánticas durante años. Una compañía llamada D-Wave ha producido y está vendiendo dispositivos que (si bien no son computadoras adecuadas y solo pueden realizar unos pocos algoritmos) explotan las propiedades cuánticas, y son otro paso incremental en el camino hacia un Turing completo. La prueba de Turing y ¿alguna vez será golpeada? ¿Qué es la prueba de Turing y alguna vez será superada? La prueba de Turing está destinada a determinar si las máquinas piensan. ¿El programa Eugene Goostman realmente pasó la prueba de Turing, o los creadores simplemente hicieron trampa? máquina cuántica.

No parece irrazonable decir que podrían ocurrir avances que permitan construir la primera computadora cuántica a gran escala en una década.

Entonces, ¿por qué tanto interés? ¿Por qué te debe importar? Las computadoras se vuelven más rápidas todo el tiempo ¿Qué es la ley de Moore y qué tiene que ver contigo? [MakeUseOf explica] ¿Cuál es la ley de Moore y qué tiene que ver con usted? [MakeUseOf explica] La mala suerte no tiene nada que ver con la Ley de Moore. Si esa es la asociación que tenía, la está confundiendo con la Ley de Murphy. Sin embargo, no estabas lejos porque la Ley de Moore y la Ley de Murphy ... - ¿Qué tienen de especial las computadoras cuánticas??

Para explicar por qué estas máquinas son tan importantes, vamos a tener que dar un paso atrás y explorar exactamente qué son las computadoras cuánticas y por qué funcionan. Para empezar, hablemos de un concepto llamado “complejidad de tiempo de ejecución.”

¿Qué es la complejidad del tiempo de ejecución?

Una de las grandes sorpresas en los primeros días de la informática fue el descubrimiento de que, si tiene una computadora que resuelve un problema de cierto tamaño en un cierto período de tiempo, duplicar la velocidad de la computadora no necesariamente le permite abordar problemas el doble de grande.

Algunos algoritmos aumentan el tiempo de ejecución total muy, muy rápidamente a medida que aumenta el tamaño del problema: algunos algoritmos se pueden completar rápidamente con 100 puntos de datos, pero completar el algoritmo con 1000 puntos de datos requeriría una computadora del tamaño de la Tierra funcionando durante mil millones de años. La complejidad del tiempo de ejecución es una formalización de esta idea: analiza la curva de cuán rápido crece la complejidad de un problema y utiliza la forma de esa curva para clasificar el algoritmo.

Generalmente, estas clases de dificultad se expresan como funciones. Se dice que un algoritmo que se vuelve proporcionalmente más difícil cuando el conjunto de datos funciona (como una función de conteo simple) es una función con una complejidad de tiempo de ejecución de “norte” (como en, se necesita norte unidades de tiempo para procesar norte puntos de datos).

Alternativamente, podría llamarse “lineal”, porque cuando lo graficas, obtienes una línea recta. Otras funciones pueden ser n ^ 2 o 2 ^ n o norte! (n factorial). Estos son polinomiales y exponenciales. En los últimos dos casos, los exponenciales crecen tan rápido que en casi todos los casos no se pueden resolver para nada, excepto ejemplos muy triviales..

Complejidad de tiempo de ejecución y criptografía

Si escuchas estas cosas por primera vez y suena sin sentido y arcano, intentemos basar esta discusión. La complejidad del tiempo de ejecución es crítica para la criptografía, que se basa en hacer que el descifrado sea mucho más fácil para las personas que conocen una clave secreta que para los que no. En un esquema criptográfico ideal, el descifrado debe ser lineal si tiene la clave, y 2 ^ k (donde k es el número de bits en la clave) si no.

En otras palabras, el mejor algoritmo para descifrar el mensaje sin la clave debería ser simplemente adivinar las posibles claves, lo cual es intratable para claves de solo unos cientos de bits de longitud.

Para la criptografía de clave simétrica (en la que las dos partes tienen la oportunidad de intercambiar un secreto de forma segura antes de comenzar la comunicación), esto es bastante fácil. Para la criptografía asimétrica, es más difícil.

La criptografía asimétrica, en la que las claves de cifrado y descifrado son diferentes y no se pueden calcular fácilmente entre sí, es una estructura matemática mucho más difícil de implementar que la criptografía simétrica, pero también es mucho más potente: la criptografía asimétrica le permite tener conversaciones privadas , incluso sobre líneas intercaladas! También te permite crear “firmas digitales” para permitirle verificar de quién vino un mensaje y que no ha sido manipulado.

Estas son herramientas poderosas y constituyen la base de la privacidad moderna: sin criptografía asimétrica, los usuarios de dispositivos electrónicos no tendrían una protección confiable contra miradas indiscretas.

Debido a que la criptografía asimétrica es más difícil de construir que simétrica, los esquemas de cifrado estándar que se usan hoy en día no son tan fuertes como podrían ser: el estándar de cifrado más común, RSA, puede descifrarse si puede encontrar eficientemente los factores primarios de un gran número. La buena noticia es que es un problema muy difícil..

El algoritmo más conocido para factorizar números grandes en sus números primos componentes se llama tamiz de campo de número general, y tiene una complejidad de tiempo de ejecución que crece un poco más lento que 2 ^ n. Como consecuencia, las claves deben ser aproximadamente diez veces más largas para proporcionar una seguridad similar, que es algo que las personas normalmente toleran como costo de hacer negocios. La mala noticia es que todo el campo de juego cambia cuando las computadoras cuánticas se lanzan a la mezcla.

Computadoras cuánticas: cambiando el juego criptográfico

Las computadoras cuánticas funcionan porque pueden tener múltiples estados internos al mismo tiempo, a través de un fenómeno cuántico llamado “superposición”. Eso significa que pueden atacar diferentes partes de un problema simultáneamente, divididas en posibles versiones del universo. También se pueden configurar de modo que las ramas que resuelven el problema terminen con la mayor amplitud, de modo que cuando abra la caja en el gato de Schrodinger, la versión del estado interno con el que es más probable que se presente sea una suficiencia. con aspecto de gato sosteniendo un mensaje descifrado.

Para obtener más información sobre las computadoras cuánticas, consulte nuestro artículo reciente sobre el tema ¿Cómo funcionan las computadoras ópticas y cuánticas? ¿Cómo funcionan las computadoras ópticas y cuánticas? La Era Exascale se acerca. ¿Sabes cómo funcionan las computadoras ópticas y cuánticas, y estas nuevas tecnologías se convertirán en nuestro futuro?? !

El resultado de esto es que las computadoras cuánticas no solo son linealmente más rápidas, de la forma en que lo son las computadoras normales: obtener dos o diez o cien veces más rápido no ayuda mucho cuando se trata de criptografía convencional que son cientos de miles de millones de veces Demasiado lento para procesar. Las computadoras cuánticas admiten algoritmos que tienen complejidades de tiempo de ejecución de crecimiento más pequeño que las que de otro modo serían posibles. Esto es lo que hace que las computadoras cuánticas sean fundamentalmente diferentes de otras tecnologías computacionales futuras, como la computación de grafeno y memrister. La última tecnología informática que debes ver para creer La última tecnología informática que debes ver para creer Mira algunas de las últimas tecnologías informáticas que están configuradas para transformar el mundo de la electrónica y las PC en los próximos años. .

Para un ejemplo concreto, el algoritmo de Shor, que solo puede ejecutarse en una computadora cuántica, puede factorizar grandes números en log (n) ^ 3 tiempo, que es drásticamente mejor que el mejor ataque clásico. Usar el tamiz de campo de número general para factorizar un número con 2048 bits lleva aproximadamente 10 ^ 41 unidades de tiempo, lo que equivale a más de un billón de billones de billones. Usando el algoritmo de Shor, el mismo problema solo toma alrededor de 1000 unidades de tiempo.

El efecto se vuelve más pronunciado cuanto más largas son las teclas. Ese es el poder de las computadoras cuánticas.

No me malinterpreten: las computadoras cuánticas tienen muchos usos potenciales no malvados. Las computadoras cuánticas pueden resolver eficientemente el problema del vendedor ambulante, permitiendo a los investigadores construir redes de envío más eficientes y diseñar mejores circuitos. Las computadoras cuánticas ya tienen usos poderosos en inteligencia artificial.

Dicho esto, su papel en la criptografía va a ser catastrófico. Las tecnologías de cifrado que permiten que nuestro mundo siga funcionando dependen de que el problema de factorización de enteros sea difícil de resolver. RSA y los esquemas de cifrado relacionados son los que le permiten confiar en que está en el sitio web correcto, que los archivos que descarga no están plagados de malware y que las personas no están espiando su navegación por Internet (si está usando Tor).

La criptografía mantiene su cuenta bancaria segura y asegura la infraestructura nuclear del mundo. Cuando las computadoras cuánticas se vuelven prácticas, toda esa tecnología deja de funcionar. La primera organización en desarrollar una computadora cuántica, si el mundo todavía funciona con las tecnologías que usamos hoy, estará en una posición terriblemente poderosa.

Entonces, ¿es inevitable el apocalipsis cuántico? Hay algo que podamos hacer al respecto? Como resultado ... sí.

Criptografía post-cuántica

Hay varias clases de algoritmos de cifrado que, hasta donde sabemos, no son significativamente más rápidos de resolver en una computadora cuántica. Estos se conocen colectivamente como criptografía post-cuántica, y brindan cierta esperanza de que el mundo pueda hacer la transición a criptosistemas que permanecerán seguros en un mundo de encriptación cuántica..

Los candidatos prometedores incluyen el cifrado basado en redes, como Ring-Learning With Error, que deriva su seguridad de un problema de aprendizaje automático demostrablemente complejo, y la criptografía multivariante, que deriva su seguridad de la dificultad de resolver sistemas muy grandes de ecuaciones simples. Puedes sobre este tema en el artículo de Wikipedia. Tenga cuidado: muchas de estas cosas son complejas, y es posible que sus conocimientos matemáticos deban reforzarse considerablemente antes de poder profundizar en los detalles..

La conclusión de mucho de esto es que los criptoesquemas post-cuánticos son muy geniales, pero también muy jóvenes. Necesitan más trabajo para ser eficientes y prácticos, y también para demostrar que son seguros. La razón por la que podemos confiar en los criptosistemas es porque les hemos arrojado suficientes genios clínicamente paranoicos durante el tiempo suficiente como para que ahora se hayan descubierto defectos obvios, y los investigadores han demostrado diversas características que los hacen fuertes.

La criptografía moderna depende de la luz como desinfectante, y la mayoría de los esquemas criptográficos post-cuánticos son simplemente demasiado nuevos para confiar en la seguridad mundial. Sin embargo, están llegando allí, y con un poco de suerte y algo de preparación, los expertos en seguridad pueden completar el cambio antes de que la primera computadora cuántica entre en línea.

Sin embargo, si fallan, las consecuencias pueden ser nefastas. La idea de que alguien tenga ese tipo de poder es inquietante, incluso si eres optimista sobre sus intenciones. La pregunta de quién desarrolla primero una computadora cuántica en funcionamiento es una que todos deben observar con mucho cuidado a medida que avanzamos en la próxima década..

¿Le preocupa la inseguridad de la criptografía para las computadoras cuánticas? ¿Cuál es tu opinión? Comparte tus pensamientos en los comentarios a continuación!

Créditos de imagen: Orbe binario a través de Shutterstock