Los investigadores han demostrado que el cifrado cuántico seguro es posible en un mundo sin problemas difíciles

Por: Ben Brubaker-Quanta Magazine.org

Supongamos que desea enviar un mensaje privado, emitir un voto secreto o firmar un documento de forma segura. Si realiza alguna de estas tareas en una computadora, dependerá del cifrado para mantener sus datos seguros. Ese cifrado debe resistir ataques de descifradores de códigos con sus propias computadoras, por lo que los métodos de cifrado modernos se basan en suposiciones sobre qué problemas matemáticos son difíciles de resolver para las computadoras.

Pero cuando los criptógrafos sentaron las bases matemáticas para este enfoque de la seguridad de la información en la década de 1980, algunos investigadores descubrieron que la dureza computacional no era la única manera de salvaguardar los secretos. La teoría cuántica, desarrollada originalmente para comprender la física de los átomos, resultó tener profundas conexiones con la información y la criptografía. Los investigadores encontraron formas de basar la seguridad de algunas tareas criptográficas específicas directamente en las leyes de la física. Pero estas tareas eran extrañamente atípicas: para todas las demás, no parecía haber alternativa al enfoque computacional clásico.

A finales del milenio, los investigadores de la criptografía cuántica pensaron que ese era el final de la historia. Pero tan sólo en los últimos años, el campo ha experimentado otro cambio sísmico.

«Ha habido una reordenación de lo que creemos que es posible con la criptografía cuántica», dijo Henry Yuen , teórico de la información cuántica de la Universidad de Columbia.

En una serie de artículos recientes, los investigadores han demostrado que la mayoría de las tareas criptográficas aún podrían realizarse de forma segura incluso en mundos hipotéticos donde prácticamente todos los cálculos son fáciles. Lo único que importa es la dificultad de un problema computacional especial sobre la propia teoría cuántica.

«Las suposiciones que necesitas pueden ser mucho, mucho, mucho más débiles», dijo Fermi Ma , criptógrafo cuántico del Instituto Simons para la Teoría de la Computación en Berkeley, California. «Esto nos está dando nuevos conocimientos sobre la dureza computacional misma».

Este mensaje se autodestruirá

La historia comienza a finales de la década de 1960, cuando un estudiante de posgrado en física llamado Stephen Wiesner comenzó a pensar en la naturaleza destructiva de la medición en la teoría cuántica. Mida cualquier sistema regido por las reglas de la física cuántica y alterará el estado cuántico que describe matemáticamente su configuración. Esta perturbación de la medición cuántica fue un obstáculo para la mayoría de los físicos. Wiesner, que adoptó una visión poco ortodoxa de la teoría cuántica centrada en la información, se preguntó si podría resultar útil. Quizás podría servir como una forma de protección integrada contra manipulaciones para datos confidenciales.

Pero las ideas de Wiesner estaban demasiado adelantadas a su tiempo y abandonó la academia después de graduarse. Afortunadamente, había discutido sus ideas con su amigo y colega físico Charles Bennett, quien intentó, sin éxito, interesar a otros en el tema durante una década. Finalmente, en 1979, Bennett conoció al informático Gilles Brassard mientras nadaba frente a la costa de Puerto Rico durante una conferencia. Juntos, escribieron un artículo innovador que describe un nuevo enfoque para una importante tarea criptográfica. Su protocolo se basó en perturbaciones de medición cuántica y no necesitaba suposiciones sobre la dificultad de ningún problema computacional.

«La naturaleza misma de la información cuántica parece algo criptográfica», dijo Ma.

El avance de Bennett y Brassard hizo que los investigadores se sintieran optimistas en cuanto a que trucos cuánticos similares podrían proporcionar una seguridad perfecta para otras tareas criptográficas. Los investigadores se centraron principalmente en una tarea llamada compromiso de bits, que es útil por sí sola y también es un componente clave de los protocolos criptográficos más avanzados.

Para entender la idea básica detrás del compromiso de bits, imagina un juego de dos jugadores en el que debes tomar una decisión secreta que luego se revela. Una forma de hacerlo es escribir la decisión en una hoja de papel y guardarla en un sobre cerrado. De esa manera, no podrás cambiar tu decisión más adelante y tu oponente no podrá echar un vistazo prematuro al resultado.

Ahora imagina que estás jugando el mismo juego en línea. Para que hacer trampa sea imposible, debes sellar la decisión en una especie de sobre digital que ninguno de los jugadores puede abrir solo. Ahí es donde entra en juego la criptografía. En 1981, el científico informático pionero Manuel Blum construyó el protocolo de compromiso del primer bit: una manera de construir sobres efectivamente imposibles de piratear a partir de problemas computacionales difíciles.

¿Pero qué tan difícil es? Los investigadores en el campo de la teoría de la complejidad computacional estudian muchos tipos diferentes de problemas difíciles, y no todos son útiles para los criptógrafos. El compromiso de bits y todos los demás protocolos criptográficos se basan en problemas de una clase que los teóricos de la complejidad llaman «NP», cuya característica definitoria es que es fácil comprobar si una solución candidata es correcta.

Desafortunadamente, los investigadores no han podido demostrar que ningún problema de NP sea realmente difícil. Todavía podría haber algún procedimiento o algoritmo inteligente por descubrir para resolver incluso los que parecen más difíciles. Si lo hubiera, entonces toda la criptografía clásica se rompería.

Estas consideraciones animaron la búsqueda de garantías de seguridad basadas en la cuántica. Pero en 1997, dos artículos demostraron que los esquemas de compromiso de bits nunca podrían ser completamente seguros si se basaran únicamente en las leyes de la física cuántica. Los artículos implicaban que sería necesario algún tipo de dureza computacional para casi todas las tareas criptográficas.

Esa fue la última palabra sobre los fundamentos teóricos de los compromisos de bits cuánticos durante casi 25 años. Luego, en 2021, un artículo de un estudiante de posgrado llamado William Kretschmer impulsó a los investigadores a enfrentar una pregunta que a nadie se le había ocurrido plantear. La dureza computacional era claramente necesaria para los compromisos de bits y la mayoría de las otras formas de criptografía, pero ¿qué tipo de dureza exactamente?

La respuesta resultaría más extraña de lo que nadie había previsto.

 

Oráculos de consultoría

El artículo de 2021 surgió de la lucha de Kretschmer por comprender una versión específica de un problema que parece conceptualmente sencillo: ¿Qué tan difícil es distinguir o discriminar entre dos estados cuánticos que parecen superficialmente similares? Kretschmer, que ahora es investigador postdoctoral en el Instituto Simons, inicialmente estaba interesado en el problema por razones que no tenían nada que ver con el compromiso del bit.

«La criptografía ni siquiera estaba en mi radar», dijo.

El problema de la discriminación fue interesante en parte porque ni siquiera estaba claro cómo describirlo usando un lenguaje matemático familiar. Los teóricos de la complejidad tradicionalmente estudian problemas con diferentes entradas posibles representadas por cadenas de bits, o 0 y 1. Para el problema de descomponer números grandes en sus factores primos, por ejemplo, esta cadena representa el número que se va a factorizar.

Incluso después de que los investigadores comenzaron a estudiar cómo se podría aprovechar la física cuántica para la computación, continuaron centrándose en esos problemas de “entrada clásica”. Los algoritmos cuánticos típicos comienzan con una cadena de bits clásica ordinaria y luego la procesan mediante trucos cuánticos. Pero en problemas de “entradas cuánticas” como el de Kretschmer, las entradas no son cadenas de bits: son estados cuánticos que se alteran tan fácilmente mediante el cálculo como mediante la medición.

«El lenguaje con el que hemos descrito los cálculos cuánticos en la teoría de la complejidad tradicional no puede hablar directamente de estos problemas», dijo Yuen.

Al principio, Kretschmer pensó que sólo necesitaba traducir el problema a un lenguaje más estándar, pero no sabía cómo. Entonces hizo lo que los teóricos de la complejidad suelen hacer cuando están desesperados: recurrió a un oráculo.

En la teoría de la complejidad, el término «oráculo» se refiere a un dispositivo hipotético que puede resolver un problema específico al instante. Una computadora con acceso a un oráculo podría resolver otros problemas más fácilmente consultando el oráculo como paso intermedio en un algoritmo. Por supuesto, los oráculos en realidad no existen en el mundo real, pero estudiarlos ayuda a los teóricos de la complejidad a comprender las relaciones entre los niveles de dificultad de diferentes problemas.

Kretschmer se preguntó qué tipo de oráculo podría facilitar la distinción de dos estados cuánticos: el llamado problema de discriminación de estados. Decidió comenzar con un oráculo especial que aumentaría el poder de los algoritmos cuánticos normales, aquellos que utilizan trucos cuánticos para resolver problemas con entradas de cadenas de bits clásicas. Estos algoritmos pueden resolver algunos problemas demasiado difíciles para los clásicos, como factorizar números grandes , pero no son omnipotentes: muchos otros problemas están fuera de su alcance.

El acceso al oráculo de Kretschmer permitiría a tales algoritmos resolver ciertos problemas de entrada clásicos que son demasiado difíciles para las computadoras cuánticas reales. Kretschmer supuso que sería excesivo, pero, para su sorpresa, demostró que el problema de la discriminación estatal aún podría dejar perplejos a estos algoritmos cuánticos mejorados.

«Me fascinó mucho el artículo de William», dijo Luowen Qian , un estudiante de posgrado que estudia criptografía en la Universidad de Boston. «De hecho, pensé que tenía que estar mal, porque es muy contradictorio».

Qian, Yuen y otros pronto demostraron que si el problema de discriminación estatal de Kretschmer fuera realmente difícil, serían posibles esquemas seguros de compromiso de bits cuánticos. Esto, a su vez, implicaría seguridad para una serie de protocolos criptográficos más avanzados. El alcance de la criptografía cuántica era mucho más amplio de lo que los investigadores de la década de 1990 habían pensado, y todo se reducía a la dureza de un problema.

¿Qué tan difícil podría ser?

El resultado de Kretschmer llegó con una gran advertencia: para que la prueba funcionara, tuvo que confiar en un oráculo inusual que sólo los algoritmos cuánticos podían consultar. ¿Quizás un oráculo más familiar facilitaría su problema de discriminación estatal y, por lo tanto, haría imposibles los compromisos seguros de bits cuánticos? En 2022, Kretschmer y Qian comenzaron a trabajar juntos para ver qué podían probar acerca de un oráculo que todos pudieran entender: uno que pudiera resolver cualquier problema NP instantáneamente. En un mundo con tales oráculos, toda criptografía clásica sería imposible.

Kretschmer pronto se dio cuenta de que el problema de la discriminación estatal estaba matemáticamente relacionado con un problema superficialmente diferente en la teoría de la complejidad cuántica, y solicitó la ayuda de dos expertos en el área, los teóricos de la complejidad Avishay Tal y Makrand Sinha . “William era realmente como un gerente y nosotros éramos contratistas”, dijo Tal.

Trabajando juntos, los cuatro investigadores demostraron rápidamente que el problema de discriminación estatal de Kretschmer aún podría ser intratable incluso para computadoras que pudieran recurrir a este oráculo NP. Eso significa que prácticamente toda la criptografía cuántica podría seguir siendo segura incluso si todos los problemas que sustentan la criptografía clásica resultaran sencillos. La criptografía clásica y la criptografía cuántica parecían cada vez más dos mundos completamente separados.

El resultado llamó la atención de Ma, y empezó a preguntarse hasta dónde podría llevar la línea de trabajo que Kretschmer había iniciado. ¿Podría la criptografía cuántica seguir siendo segura incluso con oráculos más extravagantes, que podrían resolver instantáneamente problemas computacionales mucho más difíciles que los de NP? «Los problemas en NP no son los problemas clásicos más difíciles que uno pueda imaginar», dijo Dakshita Khurana , criptógrafo de la Universidad de Illinois, Urbana-Champaign. «Hay dureza más allá de eso».

Ma comenzó a pensar en la mejor manera de abordar esa cuestión, junto con Alex Lombardi , criptógrafo de la Universidad de Princeton, y John Wright , investigador de computación cuántica de la Universidad de California, Berkeley. «Fue tan fascinante y tan alucinante que me enganché de inmediato», dijo Wright.

Después de pensar un rato en la cuestión y no llegar a ninguna parte, Ma sugirió que consideraran el caso más extremo posible: un oráculo que pudiera resolver instantáneamente cualquier problema computacional con entradas clásicas. Eso incluiría todos los problemas que los teóricos de la complejidad han estudiado tradicionalmente, incluso aquellos que se sabe que no tienen solución en el mundo real.

“Me pareció un poco loco”, dijo Lombardi.

Pero la pregunta resultó notablemente fructífera. Después de trabajar en ello durante casi un año, finalmente publicaron un resultado sorprendente . Ningún algoritmo puede consultar ese todopoderoso oráculo exactamente una vez para distinguir los dos estados cuánticos, como se requiere para socavar un esquema de compromiso de bits cuánticos.

Limitar los algoritmos a una sola consulta es una restricción menor de lo que parece, porque los algoritmos cuánticos pueden pedirle al oráculo que resuelva múltiples problemas simultáneamente explotando el fenómeno llamado superposición. Los algoritmos que pueden realizar múltiples consultas secuencialmente podrían ser más poderosos, porque pueden usar las respuestas del oráculo a consultas anteriores para decidir qué preguntar a continuación. Sigue siendo una cuestión abierta si estos algoritmos son igualmente limitados.

El artículo de Ma, Lombardi y Wright también fue significativo por otra razón. Mientras los tres investigadores luchaban con su problema, se dieron cuenta de que estaba estrechamente relacionado con un importante problema abierto planteado 16 años antes por el teórico de la complejidad Scott Aaronson y el matemático Greg Kuperberg, sobre la dificultad de transformar un estado cuántico en otro. El nuevo documento fue el primer paso significativo hacia la solución de esa cuestión.

«Es un resultado muy sólido y también muy sorprendente», afirmó Tomoyuki Morimae , investigador de criptografía cuántica en el Instituto Yukawa de Física Teórica de Kioto.

La serie de resultados recientes sugiere que el problema que parece inocuo de distinguir dos estados cuánticos no sólo es difícil, sino casi inconcebiblemente difícil: está mucho más allá del alcance de los algoritmos cuánticos normales e incluso de otros más exóticos. Esas son buenas noticias para la criptografía, pero también tienen implicaciones más amplias para los problemas computacionales cuyas entradas son estados cuánticos. La teoría tradicional de la complejidad parece incapaz de abordar estos problemas. Comprenderlos verdaderamente podría requerir un marco teórico radicalmente nuevo.

«Parece que hay algo fundamentalmente diferente en cómo se comporta la información cuántica», dijo Andrea Coladangelo , criptógrafo cuántico de la Universidad de Washington. «Seguramente tendrá conexiones que también van más allá de la criptografía».

Nota: Scott Aaronson es miembro del consejo asesor de Quanta Magazine. Su trabajo fue mencionado en este artículo pero no participó en el proceso editorial.