¿Podría la computación cuántica eventualmente usarse para hacer que el hashing moderno sea trivial para romper?

En pocas palabras, si uno construyera un dispositivo de computación cuántica con el poder de, digamos, 20 qubits, ¿podría usarse una computadora de este tipo para hacer inútil cualquier tipo de algoritmo hash moderno?

¿Sería posible aprovechar el poder de la computación cuántica en una aplicación informática tradicional?

Las computadoras cuánticas pueden tener alguna ventaja sobre las computadoras clásicas en algunos casos. El ejemplo más notable es el Algoritmo de Shor que puede factorizar un gran número en el tiempo polinomial (mientras que, clásicamente, el algoritmo más conocido requiere tiempo exponencial). Esto rompe completamente esquemas como RSA, basados ​​en la dureza de la factorización.

Este no es necesariamente el caso de las funciones hash. Primero, necesitamos definir qué significa romper una función hash. Una forma de romperlo se llama ataque previo a la imagen : me das el valor hash , y necesito encontrar un mensaje m tal que hash ( m ) = v . Otro ataque es el ataque de colisión , en el que no me das nada, y necesito presentar dos mensajes diferentes m 1 , m 2 que tienen el mismo hash hash ( m 1 ) = hash ( m 2$v$$m$$\operatorname{hash}(m)=v$$m_1, m_2$$\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$. Esto es más fácil que encontrar una preimagen, ya que no estoy obligado a una específica .$v$

¿Qué pueden hacer las computadoras Quantum? El resultado principal es el algoritmo de búsqueda de Grover : un método para que una computadora cuántica busque en una base de datos sin clasificar de tamaño con el tiempo O ( $N$(mientras que clásicamente tomará un tiempo esperado deN/2).$O(\sqrt{N})$$N/2$

Con el algoritmo de Grover, encontrar una preimagen de una función hash cuya salida es bits lleva tiempo O ( 2 k / 2 ) , en lugar de O ( 2 k ) .$k$$O(2^{k/2})$$O(2^k)$

¿Es esto un problema ? No necesariamente. Las funciones de hash están diseñadas de manera que el tiempo se considera "seguro" (en otras palabras, los diseñadores de hash siempre duplican k ). Esto se debe a la paradoja del cumpleaños con la que es posible encontrar una colisión con el tiempo O ( 2 k / 2 ) por una computadora clásica.$2^{k/2}$$k$$O(2^{k/2})$

Lo bueno del algoritmo de Grover es que es óptimo: cualquier otro algoritmo cuántico para encontrar un elemento en una base de datos sin clasificar se ejecutará en el tiempo .$\Omega(\sqrt{N})$

¿Pueden las computadoras cuánticas realizar mejores ataques de colisión ? En realidad no estoy seguro de eso. El algoritmo de Grover se puede ampliar, de modo que si hay elementos (es decir, preimágenes), el tiempo para encontrar uno se reduce a O ( $t$. Pero esto no produce colisión: ejecutar el algoritmo nuevamente podría devolver la misma preimagen. Por otro lado, si elegimosm1al azar y luego usamos el algoritmo de Grover, es probable que devuelva un mensaje diferente. No estoy seguro si esto da mejores ataques.$O(\sqrt{N/t})$$m_1$

_{(esto responde a la pregunta más general, sin restringir la computadora a 20 qubits, que no será suficiente para romper los hashes actuales de 1024 bits).}

Por lo que entiendo, la computación cuántica tiene el poder de romper fácilmente los algoritmos hash de hoy. Sin embargo, a la larga también podremos usar algoritmos de hash más complejos, y en general es más fácil encriptar que descifrar algo. Creo que los problemas más importantes a considerar son cuando la computación cuántica está disponible solo para unos pocos seleccionados, dándoles acceso fácil a cosas protegidas por los algoritmos actuales mucho antes de que se generalicen los algoritmos más avanzados o incluso la conciencia de la amenaza.

Vea aquí una respuesta realmente técnica a la pregunta sobre Desbordamiento de pila.