¿Existe alguna definición o teorema sobre lo que puede lograr una computadora cuántica a partir de la cual los esquemas criptográficos post-cuánticos (por ejemplo, la criptografía de red, pero no la criptografía cuántica) pueden justificar su seguridad? Sé que la función de búsqueda de períodos es capaz de romper RSA y registros discretos, pero ¿es el único algoritmo relevante para romper esquemas de cifrado? ¿Puedo decir que si un esquema no es susceptible a la función de búsqueda de período, no es susceptible a la computación cuántica? Si no, ¿hay alguna declaración alternativa similar de la forma "si un esquema de cifrado no puede romperse con el algoritmo X, no puede romperse con la computación cuántica"?
Por ejemplo, ¿es suficiente demostrar que un esquema de cifrado solo puede romperse probando todas las claves posibles, y lo mejor que puede hacer la computación cuántica a este respecto es el tiempo de búsqueda de raíz cuadrada con el algoritmo de Grover?
fuente
Respuestas:
Este es esencialmente el ámbito de las clases de complejidad computacional. Por ejemplo, la clase BQP puede describirse groseramente como el conjunto de todos los problemas que pueden resolverse eficientemente en una computadora cuántica. La dificultad con las clases de complejidad es que es difícil demostrar separaciones entre muchas clases, es decir, la existencia de problemas que están en una clase pero no en otra.
En cierto sentido, es suficiente para poder decir "si este algoritmo cuántico no puede romperlo, es seguro", solo tiene que usar el algoritmo correcto. Necesita un algoritmo completo de BQP, como encontrar raíces del polinomio de Jones ; cualquier algoritmo cuántico se puede convertir como una instancia de un algoritmo completo de BQP. Sin embargo, la forma en que ese algoritmo podría usarse para el craqueo no está completamente claro y no es trivial. No es suficiente ver que no se pueden forzar directamente las cosas por fuerza bruta. Entonces, ese enfoque probablemente no sea tan útil.
¿Qué queremos de un escenario cripto post-cuántico? Nosotros necesitamos:
Esta última viñeta es (esencialmente) la definición de la clase de complejidad NP: los problemas para los que puede ser difícil encontrar una solución, pero para los cuales una solución se verifica fácilmente cuando se le proporciona una prueba (correspondiente a la clave privada en nuestro caso) .
Entonces, lo que buscamos son problemas en NP pero no en BQP. Como no sabemos si NP = BQP, no sabemos que tales cosas existen. Sin embargo, hay una buena ruta para buscar soluciones: consideramos los problemas de NP completo. Estos son los casos más difíciles de problemas en NP, por lo que si BQP NP (que se cree que es el caso), los problemas de NP completo ciertamente no están en BQP. (Si un problema está completo para una clase de complejidad, significa que si puede resolverlo de manera eficiente, puede resolver todas las instancias de la clase de manera eficiente). Entonces, esta es una especie de orientación sobre dónde buscar algoritmos post-cuánticos .≠
Sin embargo, la sutileza adicional que complica las cosas es más o menos (no soy un experto) que las clases de complejidad hablan sobre la complejidad del peor de los casos, es decir, para un tamaño de problema dado, se trata de cuán difícil es la instancia más difícil del problema. Pero podría haber una sola instancia de problema, lo que significaría que si solucionamos el tamaño del problema (como es estándar, por ejemplo, podría hablar de RSA de 1024 bits; el tamaño del problema es de 1024 bits), solo habrá una clave privada. Si sabemos eso, un espía puede usar esa clave privada para descifrar mensajes. Por lo tanto, en realidad necesitamos que este razonamiento de complejidad computacional se aplique a una gran proporción de posibles entradas. Esto lo lleva al mundo de la complejidad del caso promedio donde, según tengo entendido, se hace mucho más difícil hacer tales declaraciones.
Puede ser útil hacer una comparación con RSA, un sistema criptográfico de clave pública, e ignorar la existencia de computadoras cuánticas. Se basa en la dificultad de factorizar números compuestos grandes. Este problema no está (se cree que está) en P, por lo que se cree que es difícil para un hacker con una computadora clásica obtener la respuesta. Mientras tanto, está en NP porque la solución se verifica fácilmente (si se le da un factor, puede verificarlo fácilmente). Eso significa que el destinatario legítimo puede descifrarlo utilizando una computadora clásica.
fuente
No. Solo porque su esquema criptográfico post-cuántico funcione hoy, no significa que Peter Shor no encontrará un algoritmo cuántico para romperlo mañana ".
No. Un ejemplo de otro algoritmo es el algoritmo de Grover, que es relevante para romper criptosistemas basados en el problema del logaritmo trascendental .
No. Los esquemas basados en el problema del logaritmo trascendental no son susceptibles de encontrar períodos, pero son susceptibles a aceleraciones cuánticas mejoradas.
No. No conocemos todos los algoritmos cuánticos en existencia posible. Incluso si un esquema es resistente a la búsqueda periódica y al algoritmo de Grover, podría ser posible usar computadoras cuánticas para romperlo de manera más eficiente que las computadoras clásicas. Es posible que solo necesitemos que Peter Shor se interese lo suficiente como para crear un esquema de descifrado cuántico mejorado para él.
No. El hecho de que una computadora clásica no pueda romper su esquema, excepto al probar todas las claves posibles, no significa que una computadora cuántica no pueda.
Aquí hay una pregunta que tiene una respuesta afirmativa :
¿Qué podemos hacer para demostrar que un esquema de cifrado es seguro contra las computadoras cuánticas?
Respuesta: Demuestre que descifrar el código es un problema QMA completo o QMA difícil. Los problemas difíciles de QMA son problemas difíciles para las computadoras cuánticas de la misma manera que los problemas difíciles de NP son difíciles para las computadoras clásicas.
¡Esto me ha inspirado a hacer esta pregunta, a la que no sé la respuesta!
fuente