¿Es posible que exista un método de cifrado que sea imposible de descifrar, incluso utilizando computadoras cuánticas?

Se sabe que las computadoras cuánticas pueden descifrar en el tiempo polinómico una amplia gama de algoritmos criptográficos que anteriormente se pensaba que solo podían resolverse mediante recursos que aumentaban exponencialmente con el tamaño de bits de la clave. Un ejemplo de eso es el algoritmo de Shor .

Pero, que yo sepa, no todos los problemas entran en esta categoría. Al hacer problemas difíciles para las computadoras cuánticas , podemos leer

Los investigadores han desarrollado un algoritmo informático que no resuelve problemas, sino que los crea con el fin de evaluar computadoras cuánticas.

¿Podemos esperar un nuevo algoritmo criptográfico que será difícil de descifrar incluso con una computadora cuántica ? Para mayor claridad: la pregunta se refiere específicamente al diseño de nuevos algoritmos .

El título de su pregunta solicita técnicas que son imposibles de romper, a las que One Time Pad (OTP) es la respuesta correcta, como se señala en las otras respuestas. La OTP es teóricamente segura de información, lo que significa que las habilidades computacionales de los adversarios no son aplicables cuando se trata de encontrar el mensaje.

Sin embargo, a pesar de ser perfectamente seguro en teoría , el OTP es de uso limitado en la criptografía moderna. Es extremadamente difícil de usar con éxito en la práctica. .

La pregunta importante es realmente:

¿Podemos esperar un nuevo algoritmo criptográfico que será difícil de descifrar incluso con una computadora cuántica?

Criptografía Asimétrica

La criptografía asimétrica incluye cifrado de clave pública (PKE), firmas digitales y esquemas de acuerdos clave. Estas técnicas son vitales para resolver los problemas de distribución y gestión de claves. La distribución de claves y la gestión de claves son problemas no despreciables, son en gran medida los que impiden que la OTP sea utilizable en la práctica. Internet tal como lo conocemos hoy no funcionaría sin la capacidad de crear un canal de comunicaciones seguro desde un canal de comunicaciones inseguro, que es una de las características que ofrecen los algoritmos asimétricos.

Algoritmo de Shor

El algoritmo de Shor es útil para resolver los problemas de factorización de enteros y logaritmos discretos. Estos dos problemas son los que proporcionan la base para la seguridad de esquemas ampliamente utilizados como RSA y Diffie-Hellman .

NIST es Actualmente, evaluando envíos para algoritmos Post-Quantum , algoritmos que se basan en problemas que se cree que son resistentes a las computadoras cuánticas. Estos problemas incluyen:

• Problemas basados ​​en celosías
  • Problema de vector más corto (SVP)
  • Problema de vector más cercano (CVP)
• Ecuaciones multivariadas
  • Ecuaciones polinomiales multivariadas
• Esquemas basados ​​en código
  • Basado en la dureza de decodificar códigos lineales
• Isogeny Supersingular Diffie-Hellman (SIDH)

Cabe señalar que pueden existir algoritmos clásicos para resolver los problemas anteriores , es solo que el tiempo de ejecución / precisión de estos algoritmos es prohibitivo para resolver grandes instancias en la práctica. Estos problemas no parecen ser solucionables cuando se les da capacidad de resolver el problema de la búsqueda de pedidos , que es lo que hace la parte cuántica del algoritmo de Shor.

Criptografía Simétrica

Algoritmo de Grover proporciona una aceleración cuadrática al buscar en una lista sin clasificar. Este es efectivamente el problema de la fuerza bruta de una clave de cifrado simétrica.

Trabajar alrededor del algoritmo de Grover es relativamente fácil en comparación con trabajar alrededor del algoritmo de Shor: simplemente duplique el tamaño de su clave simétrica . Una clave de 256 bits ofrece 128 bits de resistencia contra la fuerza bruta a un adversario que utiliza el algoritmo de Grover.

El algoritmo de Grover también se puede usar contra funciones hash . La solución de nuevo es simple: duplicar el tamaño de la producción de hash (y la capacidad si está utilizando un hash basado en una construcción de esponja ).

Supongo que hay un tipo de encriptación que no se puede descifrar usando computadoras cuánticas: una almohadilla única como el cifrado Vigenère . Este es un cifrado con un teclado que tiene al menos la longitud de la cadena codificada y se usará solo una vez. Este cifrado es imposible de descifrar incluso con una computadora cuántica.

Explicaré por qué:

Asumamos que nuestro texto plano es ABCD. La clave correspondiente podría ser 1234. Si lo codificas, entonces obtienes XYZW. Ahora puede usar 1234para obtener ABCDo 4678para obtener EFGHlo que podría ser una oración válida también.

Entonces, el problema es que nadie puede decidir si quiso decir ABCDo EFGHno su clave.

La única razón por la que se puede descifrar este tipo de cifrado es porque los usuarios son flojos y usan una clave dos veces. Y luego puedes intentar descifrarlo. Otros problemas son, como @peterh declaró que los pads únicos requieren que se comparta un canal secreto

Sí, hay muchas propuestas de algoritmos criptográficos post-cuánticos que proporcionan las primitivas criptográficas a las que estamos acostumbrados (incluido el cifrado asimétrico con claves privadas y públicas).

Para dar seguimiento a la respuesta de Ella Rose: los esquemas de cifrado más prácticos que se usan hoy en día (p. Ej., Diffie-Hellman, RSA, curva elíptica, basados ​​en celosía) se centran en la dificultad de resolver el problema de subgrupos ocultos (HSP). Sin embargo, los tres primeros se centran en el HSP para grupos abelianos . El HSP para grupos abelianos se puede resolver de manera eficiente mediante la transformación cuántica de Fourier , que se implementa, por ejemplo, mediante el algoritmo de Shor. Por lo tanto, son vulnerables al ataque de una computadora cuántica. La mayoría de los métodos basados ​​en celosía, por otro lado, giran en torno al HSP para diédricogrupos, que no son belicos. No se cree que las computadoras cuánticas sean capaces de resolver eficientemente el HSP no belga, por lo que estos algoritmos deberían ser capaces de implementar la criptografía post-cuántica.