¿Podrían las computadoras cuánticas descifrar algún cifrado? [cerrado]

Me han dicho que los físicos y los científicos informáticos están trabajando en computadoras que podrían usar la física cuántica para aumentar significativamente las capacidades de cómputo y descifrar cualquier cifrado para que la criptografía pierda sentido.

¿Es verdad?

Lectura relacionada: ¿Cómo cambiará la criptografía la computación cuántica? (y probablemente un poco en la etiqueta de criptografía posterior a la cuántica de Cryptography y la etiqueta de computación cuántica de Information Security ).
Voto para cerrar esta pregunta como fuera de tema porque se trata de verificar la afirmación del uso de una computadora cuántica y no sobre física. Quizás Criptografía o Escépticos podrían ser más adecuados para esta pregunta.
De hecho, no creo que este sea un tema para nosotros. Realmente es una pregunta sobre criptografía: la única conexión con la física es saber que una computadora cuántica puede resolver efectivamente ciertos problemas en un tiempo menos que exponencial.
Ni siquiera creo que sea tan importante. Respondí una pregunta similar hace un tiempo, ¿cómo cambiará la criptografía la computación cuántica? , y el tdlr de esto fue que sabemos cómo lidiar con las computadoras cada vez más rápidas: espacios de teclas más grandes.
@NathanCooper Si puedo construir una máquina cuya capacidad de factorización crezca más rápido que la capacidad de su máquina para cifrar/descifrar, entonces los espacios de claves más grandes no ayudan. ¿O me estoy perdiendo algo?
@DanielSank si...
@emory por supuesto "si". El punto es que lo que dijo Nathan no tiene sentido para mí.
Creo que los 24 votos a favor y las múltiples respuestas exitosas sugieren que esta pregunta fue apropiada. Sugiero reabrirlo. Esta es una pregunta popular relacionada con la computación cuántica; ciertamente es una pregunta interdisciplinaria, pero el hecho de que sea interdisciplinaria no significa que no pueda responderse o que esté fuera de tema para este foro.

Respuestas (7)

No, no es.

Las computadoras cuánticas pueden factorizar grandes números de manera eficiente, lo que permitiría romper muchos de los criptosistemas de clave pública de uso común, como RSA, que se basan en la dureza de la factorización.

Sin embargo, existen otros criptosistemas, como la criptografía basada en celosías, que no se basan en la dureza de la factorización y que (según nuestro conocimiento actual) no serían vulnerables al ataque de una computadora cuántica.

La computación cuántica es muy prometedora, pero no es infinitamente poderosa.

Las afirmaciones (exageradas) que ha escuchado probablemente se basan en el algoritmo de computación cuántica más famoso, el algoritmo de Shor . Este es un método para usar una computadora cuántica para factorizar números enteros en números primos. Resulta que muchos esquemas de encriptación se basan en el hecho de que factorizar números grandes es muy difícil. Los mensajes se pueden cifrar con bastante facilidad de tal manera que solo alguien que conozca la factorización prima de un número en particular puede descifrarlos con un esfuerzo razonable. Si pudiera factorizar rápidamente números grandes, rompería muchos esquemas de encriptación actuales.

Sin embargo, existen otras técnicas que no se ven inmediatamente amenazadas por las computadoras cuánticas. Por lo menos, siempre puede usar un bloc de notas de una sola vez, siempre que el mensaje en sí. Esto es matemáticamente indescifrable, ya que cualquier mensaje puede ser "descifrado" del cifrado con la suposición adecuada de la clave, por lo que no hay forma de que un intruso sepa el mensaje real.

La computación cuántica también puede abrir las puertas a formas de transmisión de información seguras de próxima generación. Por ejemplo, la mayor parte del cifrado actual es solo eso: codificar el mensaje para que solo el destinatario pueda entenderlo. Pero puede haber buenas formas cuánticas de garantizar físicamente que los intrusos no puedan acceder a la transmisión en primer lugar.

Entonces, ¿las computadoras cuánticas ayudarían a los espías a obtener ventaja sobre los encriptadores o al revés? Parece que el descifrado se vuelve más fácil en algunos casos, pero un buen cifrado también se vuelve más fácil.
Para los blocs de notas de un solo uso, el cifrado se vuelve más caro y menos seguro, ya que el bloc tiene que enviarse físicamente al cifrador, quien tiene que asegurarse de que The Bad Guys no lo lea. Para flujos de tráfico muy grandes, las plataformas también aumentan de tamaño, por lo que hay un costo. Sin embargo, mientras la clave permanezca segura, los espías son indefensos y las computadoras cuánticas son inútiles.
Pero en muchos casos, escuchar a escondidas no es el problema. Por ejemplo, digamos que tengo un archivo en mi disco duro que no quiero que nadie lea, incluso si me roban la máquina.
@innisfree La mecánica cuántica ayuda a los encriptadores más que a los fisgones, ya que la distribución de claves cuánticas hace que las libretas de un solo uso sean viables en un canal inseguro. Los sistemas actuales están diseñados de tal manera que cualquier intruso provocaría un colapso de la función de onda, destruyendo la OTP en el proceso. También tenga en cuenta que el algoritmo de Shor es en gran medida una vulnerabilidad teórica (en el momento de escribir este artículo, el número más grande que se ha factorizado es 56153), mientras que estos sistemas QKD están en uso hoy en día.

De hecho, hay toda una clase de complejidad dedicada a la respuesta, que es "no, no puede descifrar ningún código". La clase se conoce como BQP , o "tiempo polinomial cuántico de error acotado". Es la clase de problemas de decisión que puede resolver una computadora cuántica en tiempo polinomial, con un margen de error de no más de 1/3 (este término de error se tiene en cuenta en un paso de cálculo clásico que ocurre después de la mayoría de los algoritmos cuánticos para verificar que los resultados son correctos).

Se cree que BQP tiene las siguientes relaciones con otras complejidades:

  • Contiene P (tiempo polinomial)
  • Intersecta, pero probablemente no contiene completamente NP (Tiempo polinomial no determinista)
    • Probablemente no contiene NP-completo (como corolario)
  • Subconjunto de PSPACE (Problemas que se pueden resolver con requisitos de espacio polinomial)

(La principal incógnita en esa lista es que aún no se sabe si P=NP. La lista asume P!=NP, pero si P=NP, claramente NP y NP-completo también serían parte de BQP. Tampoco No sé si NP=BQP o no. ¡Queda mucho por descubrir! )

RSA se puede descifrar usando computadoras cuánticas porque la tarea de factorizar grandes números compuestos está en BQP, como lo demuestra el algoritmo de Shor. El algoritmo de Shor es NP (pero no NP-completo). Hay otros algoritmos NP que se cree que están fuera de BQP y que se pueden usar para el cifrado (la respuesta aceptada se relaciona con la criptografía basada en celosía, que es una de esas clases de algoritmos).

"La única incógnita en esa lista es que aún no se sabe si P=NP". -- La relación exacta de NP y BQP también se desconoce.

Hasta ahora, las respuestas se han centrado en el cifrado de clave pública, en el que alguien publica una clave pública que se puede usar para cifrar mensajes y que no es secreta. Se sabe que las computadoras cuánticas son eficientes para resolver varios de los problemas más comúnmente utilizados como base de la criptografía de clave pública. No afecta a toda la criptografía de clave pública, solo a los esquemas más populares; sí afecta a los esquemas más populares.

Sin embargo, hay más en el cifrado que la clave pública. Se cree que los esquemas de cifrado simétrico, en los que las dos partes comparten una clave secreta, no están sujetos a más que una aceleración cuadrática con computadoras cuánticas (las computadoras cuánticas pueden lograr una aceleración cuadrática para problemas generales de búsqueda, pero no más). Esto corresponde a reducir a la mitad la longitud de la clave. A diferencia de los sistemas comunes de clave pública, es extremadamente fácil responder a la reducción efectiva a la mitad de la longitud de la clave: puede simplemente duplicar la longitud de la clave y continuar. El cifrado simétrico es extremadamente común; incluso cuando se usa el cifrado de clave pública, generalmente se usa para intercambiar una clave por un cifrado simétrico.

El sistema simétrico más común, AES, tiene una variante de clave de 256 bits que brinda 128 bits de seguridad contra computadoras cuánticas. Otros esquemas en desarrollo admiten claves de 512 bits, lo que proporcionaría 256 bits de seguridad efectiva. Se cree que tanto 128 como 256 bits serán seguros en el futuro previsible.

Del mismo modo, se cree que las funciones hash criptográficas resisten muy bien a las computadoras cuánticas. Existe el mismo ataque basado en el algoritmo de Grover, pero al igual que con las funciones de cifrado, es fácil de contrarrestar.

Por lo tanto, cualquier afirmación de que la criptografía pierde sentido está totalmente fuera de lugar, porque lo único que se ve seriamente afectado son los sistemas de clave pública. Los sistemas de clave pública son importantes, pero la criptografía es un campo mucho más amplio.

Y esta respuesta es precisamente la razón por la que siento que esta pregunta está fuera de tema aquí: no hay una gota de física aquí (algo que esperamos que esté en cada respuesta).
@KyleKanos: Hay una gota de física aquí, en el algoritmo de Grover, que tenía suficiente física en 1997 para publicarse en Phys. Rev. Lett. ($$) ( versión arXiv ). Lo admito, es solo una gota de física, pero saber si es física o informática es un problema común (y frustrante) con la información cuántica.

No. No puede existir una computadora X que pueda descifrar cualquier cifrado porque el bloc de notas de un solo uso es un cifrado y el bloc de notas de un solo uso no se puede descifrar mediante un algoritmo (prueba trivial en la teoría de la información).

Me gustaría agregar que las computadoras cuánticas no pueden descifrar ningún código existente porque sus puertas lógicas pueden realizar las mismas operaciones que las puertas lógicas clásicas. Agregan nuevas posibilidades manteniendo las que antes eran posibles en las computadoras clásicas.

Dado que los programas, en esencia, funcionan en puertas lógicas, es razonable suponer que cualquier código existente para computadoras clásicas puede funcionar en una computadora cuántica.

Véase también puerta cuántica en wikipedia.

Esto no tiene sentido. ¿Cómo decir que una computadora cuántica puede hacer todo lo que una computadora clásica puede hacer descarta la posibilidad de que las computadoras cuánticas puedan descifrar códigos? Especialmente dado que las computadoras clásicas pueden descifrar códigos, pero no necesariamente en una cantidad de tiempo factible. Su argumento es como decir: "Los montacargas no pueden levantar 20 kg porque pueden levantar cualquier cosa que pueda levantar un ser humano". Se equivoca dos veces: los humanos pueden levantar 20 kg y, aunque no pudieran, la carretilla elevadora puede hacer más.

Ok, en teoría, una computadora cuántica podría funcionar así:

Puede iniciar un cálculo normal y calcularlo en paralelo para todas las claves de entrada posibles. Lo que significa que descifrar un texto cifrado con la clave correcta lleva tanto tiempo como descifrarlo con todas las claves posibles (con una longitud fija). Esto significaría que todos los métodos de encriptación tradicionales como AES, etc. podrían descifrarse tan rápido como el titular de la clave legal podría descifrarlos.

La parte complicada (donde sobresale el pad de una sola vez) es cómo saber si el mensaje resultante que recibió al descifrar es realmente el texto correcto. Por ejemplo te envío el Mensaje OKencriptado con AES 256bit. Ahora hay 2 ^ 256 claves posibles para descifrar este mensaje y todas ellas darán algún resultado. Muchos tal vez en algo como #§u otros símbolos de bytes crípticos, pero algunas claves pueden conducir a dos letras "WB" y alguna combinación puede incluso conducir a "NO".

Entonces, la parte difícil es descubrir cuál es el mensaje correcto. Debido a que la computadora cuántica (teórica) al final solo generará algunos resultados con alta probabilidad, por lo que debe codificar una verificación, que discernirá si la salida es realmente un texto válido. Si el texto es mucho más grande que la clave y algo así como inglés simple, o mejor, un formato estándar que se puede verificar para verificar la integridad, esto podría ser posible. Pero si hay varios resultados posibles que parecen válidos, un humano tendrá que clasificarlos, por lo que, en el caso de un bloc de notas de una sola vez, descifrar el código es tan bueno como simplemente adivinar de la nada. Es posible que se deban adaptar otros esquemas de encriptación para producir mensajes que parezcan válidos para claves falsas, pero esto parece posible...

--

Esto solo funcionaría si una computadora cuántica real pudiera funcionar así. Hasta donde yo sé, no tenemos evidencia sólida de que un control de calidad realmente funcione así. Así que tal vez simplemente no se pueda hacer y ni siquiera tengamos un problema ;-)

Así no es como funcionan las computadoras cuánticas. La creencia de que pueden es tan común que el Dr. Aaronson tiene una sección completa de su blog dedicada a este concepto erróneo: Hablando de la verdad al paralelismo . Dan aceleraciones para algunos problemas, pero no tantos como eso sugeriría. (Básicamente, no creemos que BQP = PSPACE).
Hay muchos artículos en esa categoría, si bien es cierto que los memresistores o tecnologías similares sufren varios problemas (como codificar la salida), una computadora cuántica podría resolver fundamentalmente un problema complejo con una alta probabilidad. Y si puede ajustar la probabilidad lo suficientemente alto, para tener una precisión del 99,99 % con algunas ejecuciones, eso es prácticamente lo suficientemente bueno y podría resolver los problemas mencionados, si alguien pudiera construir un control de calidad de este tipo.
El problema fundamental es que las computadoras cuánticas no le permiten calcular todas las entradas posibles en paralelo: la computación cuántica no es no determinista.
Incluso si la cifra del 99,99 % fuera correcta (que, como se explicó, no lo es), el 0,01 % de 2^256 sigue siendo aproximadamente 1e73, que es una gran cantidad de claves que quedan por probar. De hecho, valen unos 242 bits. (2^242 ~ 7.07e72) Por lo tanto , la reducción del 99,99% le otorga una optimización de 14-15 bits a partir de una clave de 256 bits. Impresionante, sí (muchos otros ataques tienden a mordisquear algunos bits del espacio de búsqueda a la vez, como máximo , a menudo con variantes de rondas reducidas), pero muy lejos de ser una ruptura total. Supongo que muchos PRNG son peores que eso, especialmente si están mal sembrados en el momento de la generación de claves.
Recuerde el "suponga que su adversario es capaz de un billón de conjeturas por segundo" de Snowden (ciertamente sobre las frases de contraseña de PGP, pero aún así, es una línea de base razonable para la comparación, y la diferencia puede ascender a quizás unos pocos órdenes de magnitud más o menos). Un billón es 1e12. Eso nos deja con 1e61 segundos, más o menos. Se estima que el universo tiene alrededor de 1e17 segundos de antigüedad. Muy generosamente hablando, estás viendo 1e40 veces la edad del universo.
Lo que estás describiendo es una computadora no determinista (la "N" en "NP"). Si bien no sabemos con certeza si las computadoras cuánticas no son equivalentes a las no deterministas (ni siquiera sabemos que PAGS ≠ norte PAGS ), estamos bastante seguros de que no lo son.
-1 Esta respuesta indica que BQP = NP , que se cree ampliamente que es falso. Usando el Algoritmo de Grover , las computadoras cuánticas pueden acelerar las búsquedas de fuerza bruta por un factor de raíz cuadrada, lo que significa que podría usar fuerza bruta en una clave AES de 256 bits en solo 2^128 operaciones. Pero eso sigue siendo una complejidad exponencial.
¿Podrían las computadoras cuánticas descifrar algún cifrado? [cerrado]
RespuestasAquíPolítica de privacidad1y, 0v