¿Por qué la gente está tan interesada en la criptografía post-cuántica, dado que nadie se ha acercado a construir una computadora cuántica real o lo hará pronto?

No creo que veamos que la computación cuántica se convierta en una amenaza para los algoritmos existentes “en el corto plazo”. De hecho, en los últimos 15 años, el progreso en esto ha estado en el extremo más lento del rango que pensé cuando se publicó el Algoritmo de Shor. Pero …

El trabajo es útil de todos modos.

Todavía no tenemos una prueba de que la factorización o los problemas de logaritmo discreto generalizado sean NP. [Actualización: vea la discusión en los comentarios sobre por qué simplemente escribí “NP” en lugar del más específico “NP-complete”.] Por lo tanto, no podemos probar que un escenario como en la película Sneakers (1992) de factorización de tiempo rápida y polinómica no está a la vuelta de la esquina, incluso sin computadoras cuánticas, rompiendo así el RSA. (Y lo mismo vale para DH / ECC).

La búsqueda de criptografía “post-cuántica” se superpone fuertemente con la búsqueda de criptografía de clave pública basada en problemas probablemente difíciles. Realmente no entiendo la criptografía basada en la red lo suficiente como para decir algo específico, pero entiendo que su problema subyacente es probablemente NP y probablemente difícil contra los algoritmos cuánticos. Puede que no sea una coincidencia que tenga ambas propiedades.

Especulación e incertidumbre

Ahora sospecho que la dificultad de construir y ejecutar una computadora cuántica del tipo relevante crece exponencialmente con el número de qubits, por lo que un aumento lineal en el tamaño de la clave para RSA y GLP aún empujará y un aumento exponencial en el trabajo para el atacante . Así que realmente estamos a salvo de las computadoras cuánticas y que, en el peor de los casos, es posible que tengamos que aumentar el tamaño de las claves (como lo hacemos con los aumentos de hardware más mundanos).

Pero podría estar equivocado en mi visión pesimista de construir las computadoras cuánticas relevantes. Lo que he ofrecido allí es principalmente especulación. No estoy seguro de querer apostar la granja en mi especulación e intuiciones.

Actualización: Ignorar D-Wave

Es posible que haya visto comunicados de prensa e informes de prensa sobre D-Wave, una compañía que entrega computadoras que llaman computadoras cuánticas con muchos cientos de qubits. Tenga en cuenta que D-Wave utiliza las palabras “computadoras cuánticas” y “qubits” en formas que, en el mejor de los casos, son completamente irrelevantes para las preguntas de la criptografía cuántica.

Malcom desafía correctamente la afirmación “no en el corto plazo”, y hace referencia a Dwave 1x, una máquina experimental.

Esta semana, Dwave anunció la primera computadora cuántica disponible comercialmente del mundo, D-Wave Systems anuncia la disponibilidad general de la computadora cuántica 1000+ Qubit D-Wave 2X

Mucho más por hacer y Dwave no está configurado exactamente para el cifrado. ¡El juego comienza! Vea el comentario de John Baily a continuación, y su referencia sobre el rendimiento del sistema Dwave, [1508.05087] Evaluación comparativa de un procesador de recocido cuántico con la métrica de tiempo hasta el objetivo.

Si la pregunta es solo retórica, estoy de acuerdo con el punto. Clasifico el desafío de la computación cuántica como similar al desafío de la energía de fusión nuclear, ambos necesitan grandes avances en física más una ingeniería sólida para llevar las tecnologías a casa. Tampoco es probable durante unos 10 a 15 años.

Si la pregunta es sencilla: ¿cuál es la base del interés? Hablando por mí mismo, me uní a la división de computadoras RCA en un momento en que todavía usaban tubos. Aprender a aplicar la lógica a los circuitos fue novedoso. Mi primer mentor fue un estudiante de matemáticas. Madurar en ese contexto fue estimulante. La lógica cuántica extiende muy bien el desafío. Mi próximo obstáculo personal es escribir algo útil usando el Quantum Computing Playground de Google.

En cuanto a la motivación / interés de los demás, particularmente aquellos que hacen preguntas salvajes sobre la computación cuántica en Quora, solo puedo especular. Mi conjetura es que la mayoría se basa en la incomprensión de la tecnología debido a la hipérbole salvaje del escritor de ciencias.

Hay dos aspectos de la computación cuántica que la mayoría de los interrogadores parecen haberse perdido:

1. La velocidad avanzada tiene un precio: no se puede acceder directamente a los qubits enredados, pero requieren un procesamiento sofisticado para recuperar información útil.
2. Las puertas cuánticas probablemente necesiten un enfriamiento criogénico. El uso en el hogar sin un refrigerador / aire acondicionado 100 veces más grande requeriría otro avance tecnológico.

El principal problema es su última cláusula, “o lo hará pronto”. Yo, personalmente, creo que llegará antes de lo que piensas.

Tal vez no te convenza la oferta de D-Wave. Pero el hecho de que hayan hecho una oferta significa que probablemente estamos en el mismo estado con la computación cuántica ahora, como lo estaban con la computación convencional en la década de 1930.

Si es así, podríamos estar a solo una década de tener una máquina que, en las manos equivocadas, pueda descifrar la mayoría de los sistemas de seguridad existentes.
“Ahora” es precisamente el momento adecuado para comenzar a encontrar soluciones a eso, antes de que suceda.

No puedo decir por qué hay tantos interesados, si te refieres a por qué es actualmente popular, pero la criptografía es matemática, y la matemática es intrínsecamente interesante independientemente del uso. Hay muchas ramas de las matemáticas que solo se volvieron “útiles” mucho más tarde, y otras que aún no han encontrado un nicho comercial. La matemática se trata de tomar las restricciones de un sistema y resolver las propiedades. No importa si esas restricciones aparecen en nuestro universo o no.

Todo lo que está cifrado hoy con los sistemas criptográficos actuales se volverá vulnerable cuando construyamos una computadora cuántica. Podemos esperar mucho mejor sobre cualquier cosa encriptada con un sistema post-cuántico. Por qué esperar ?