1978 El criptosistema resiste el ataque cuántico

Nadie ha construido una computadora cuántica mucho más poderosa que una calculadora de bolsillo, pero eso no ha impedido que la gente se preocupe por las implicaciones del mundo de la computación post-cuántica. Los más preocupados son las personas que dependen de los códigos criptográficos para proteger la información confidencial. Cuando se enciende la primera computadora cuántica de tamaño decente, los códigos previamente seguros, como el algoritmo RSA de uso común, se volverán instantáneamente rompibles.

Es por eso que los criptógrafos se apresuran a buscar códigos que sean seguros en el mundo post-cuántico. Hoy, Hang Dinh de la Universidad de Connecticut y un par de amigos muestran que los criptógrafos han estado mirando a uno todo el tiempo. Dicen que un código poco utilizado desarrollado por el matemático de CalTech Robert McEliece en 1978 puede resistir todos los ataques conocidos de las computadoras cuánticas.

Primero, hagamos una distinción entre códigos simétricos y asimétricos. Los códigos simétricos utilizan claves idénticas para cifrar y descifrar un mensaje. Las computadoras cuánticas pueden acelerar dramáticamente un ataque contra este tipo de códigos. Sin embargo, los códigos simétricos tienen cierta protección. Duplicar el tamaño de la clave contrarresta esta aceleración. Por lo tanto, es posible que los creadores de códigos se mantengan por delante de los rompedores, al menos en teoría. (Aunque en la práctica, el dinero seguro estaría en el depredador en este juego del gato y el ratón).

Los códigos asimétricos utilizan diferentes claves para cifrar y descifrar mensajes. En los denominados sistemas de cifrado de clave pública, como el popular algoritmo RSA, una clave pública está disponible para cualquiera que pueda utilizarla para cifrar un mensaje. Pero solo aquellos con una clave privada pueden descifrar los mensajes y esto, por supuesto, se mantiene en secreto.

La seguridad de estos sistemas se basa en las llamadas funciones de trampilla: pasos matemáticos que son fáciles de realizar en una dirección pero difíciles de realizar en la otra. El ejemplo más famoso es la multiplicación. Es fácil multiplicar dos números para obtener un tercero, pero es difícil comenzar con el tercer número y determinar cuáles dos lo generaron, un proceso llamado factorización.

Pero en 1994, el matemático Peter Shor ideó un algoritmo cuántico que podría factorizar mucho más rápido que cualquier contraparte clásica. Un algoritmo de este tipo que se ejecuta en una computadora cuántica decente podría romper todos los sistemas de cifrado de clave pública conocidos como un niño de 4 años que se vuelve loco en Legoland.

Aquí tienes una idea de cómo funciona. El problema de la factorización es encontrar un número que se divida exactamente en otro. Los matemáticos hacen esto usando la idea de periodicidad: un objeto matemático con exactamente la periodicidad correcta debería dividir el número exactamente, cualquier otro no lo hará.

Una forma de estudiar la periodicidad en el mundo clásico es utilizar el análisis de Fourier, que puede descomponer una señal en sus ondas componentes. El análogo cuántico de esto es el muestreo de Fourier cuántico y el triunfo de Shor fue encontrar una manera de utilizar esta idea para encontrar la periodicidad del objeto matemático que revela los factores.

Gracias a Shor, cualquier código que se base en este tipo de asimetría (es decir, casi todos los sistemas populares de cifrado de clave pública) se puede descifrar mediante un ataque de Fourier cuántico.

El criptosistema de McEliese es diferente. También es asimétrico, pero su seguridad no se basa en la factorización, sino en una versión de un acertijo que los matemáticos denominan el problema oculto de los supgrupos. Lo que han demostrado Dinh y sus colegas es que este problema no se puede resolver mediante el análisis de Fourier cuántico. En otras palabras, es inmune al ataque del algoritmo de Shor. De hecho, es inmune a cualquier ataque basado en el muestreo cuántico de Fourier.

Eso es un gran problema. Significa que cualquier cosa codificada de esta manera estará segura cuando la próxima generación de computadoras cuánticas comience a devorar los criptosistemas de clave pública más convencionales. Uno de esos sistemas es Entropy, una red de comunicaciones de igual a igual diseñada para resistir la censura basada en el criptosistema McEliese.

Pero la entropía se usa poco y hay buenas razones por las que otros se han resistido al sistema de cifrado de McEliese. El principal problema es que tanto la clave pública como la privada son algo difíciles de manejar: una clave pública estándar es una matriz grande descrita por no menos de 2 ^ 19 bits.

Eso puede parecer un problema menor ahora. Es posible que el sistema McEleise se convierta repentinamente en el foco de mucha más atención más de 30 años después de su invención.

Sin embargo, vale la pena señalar que, si bien el nuevo trabajo garantiza la seguridad contra todos los ataques cuánticos conocidos, no hace nada por el estilo para futuros ataques cuánticos. Es perfectamente posible que alguien desarrolle un algoritmo cuántico que lo destroce tan fácilmente como lo puede hacer Shor con el algoritmo RSA. Nuestros resultados no descartan otros ataques cuánticos (o clásicos), dicen Dinh y compañía.

Por tanto, el escenario más probable para la investigación futura es que los criptografistas renovarán sus esfuerzos en una de las otras direcciones que parecen fructíferas, como los algoritmos basados ​​en celosías y la criptografía multivariante.

De cualquier manera, espere escuchar mucho más sobre la criptografía postcuántica, siempre que se cuente con los poderes que se le permitan.

Ref: arxiv.org/abs/1008.2390 : El criptosistema McEliece resiste los ataques de muestreo cuántico de Fourier

esconder