On the hardness of the hidden subspaces problem with and without noisecryptanalysis of Aaronson-Christiano’s quantum money scheme

Resumen

El boom de internet ha marcado el comienzo de la era digital y ésta ha traído consigo un desarrollo espectacular de las tecnologías de la información y de las comunicaciones, entre las que la criptografía es la reina. La criptografía de clave pública actual está basada principalmente en dos problemas que la comunidad criptográfica asume como difíciles: la factorización y el logaritmo discreto. Sin embargo, si se llegase a construir un computador cuántico lo suficientemente potente, esta dificultad no sería tal. Así pues, la computación cuántica pondría en un grave aprieto a la criptografía moderna y, puesto que la trayectoria reciente del campo sugiere que ésta podría convertirse en una realidad en un futuro no muy lejano, la comunidad criptográfica ha comenzado a explorar otras opciones para estar lista en caso de que se logre construir un computador cuántico eficiente. Esto ha dado un im- pulso a lo que se conoce como criptografía post-cuántica, aquella cuya dificultad no se vería afectada por este nuevo paradigma de computación y que está basada en los llamados problemas resistentes a la computación cuántica. La criptografía post-cuántica ha suscitado mucho interés recientemente y actualmente está en proceso de estandarización, por lo que en el momento de iniciar esta tesis resultaba relevante estudiar problemas supuestamente resistentes al computador cuántico. La parte central de esta tesis es el análisis de la dificultad del problema de los subespacios ocultos (HSP por sus siglas en inglés) y del problema de los subespacios ocultos con ruido (NHSP), dos problemas resistentes al computador cuántico según sus autores. Además de la relevancia que su supuesta resistencia a la computación cuántica les confiere, estos dos problemas son también importantes porque en su dificultad se sustenta la seguridad de las dos versiones del primer esquema de dinero cuántico de clave pública que cuenta con una prueba de seguridad. Este primer esquema es el de Aaronson-Christiano, que implementa dinero cuántico — un tipo de dinero que explota las leyes de la mecánica cuántica para crear dinero infalsificable — que cualquiera puede verificar. Los resultados obtenidos acerca de la dificultad del HSP y del NHSP tienen un impacto directo sobre la seguridad del esquema de Aaronson-Christiano, lo cual nos motivó a centrar esta tesis en estos dos problemas. El Capítulo 3 contiene nuestros resultados acerca del problema de los subespacios ocultos y está fundamentalmente basado en nuestro trabajo [Conde Pena et al.,2015]. Los autores del HSP lo definieron originalmente sobre el cuerpo binario, pero nosotros extendemos la definición a cualquier otro cuerpo finito de orden primo, siempre considerando que la instanciación es la que los autores proponen. Después de modelar el HSP con un sistema de ecuaciones con buenas propiedades, usamos técnicas de criptoanálisis algebraico para explorar el sistema en profundidad. Para el HSP sobre cualquier cuerpo que no sea el binario diseñamos un algoritmo que resuelve de manera eficiente instancias que satisfacen una cierta condición. Utilizando técnicas distintas, construimos un algoritmo heurístico, sustentado por argumentos teóricos, que resuelve eficientemente instancias del HSP sobre el cuerpo binario. Ambos algo-ritmos comprometen la dificultad del HSP siempre que las instancias del problema sean escogidas como Aaronson-Christiano proponen. Como consecuencia, nuestros algoritmos vulneran la seguridad de la versión del esquema sin ruido. El capítulo 4 contiene nuestros resultados acerca del problema de los subespacios ocultos con ruido y está fundamentalmente basado en nuestro trabajo [Conde Pena et al., 2018]. Al igual que con el HSP, extendemos la definición del NHSP a cualquier otro cuerpo de orden primo y consideramos instancias generadas como especifi- can Aaronson-Christiano. Mostramos que el NHSP se puede reducir al HSP sobre cualquier cuerpo primo que no sea el binario para ciertas instancias, mientras que el NHSP sobre el cuerpo binario se puede resolver con una probabilidad mayor de la asumida por los autores en la conjetura sobre la que la seguridad de su esquema con ruido se sustenta. Aunque nuestros resultados se obtienen desde un punto de vista puramente no cuántico, durante el desarrollo de esta tesis otro autor demostró que existe una reducción cuántica del NHSP al HSP también en el caso binario. Por tanto, la dificultad del NHSP y la seguridad del esquema de Aaronson-Christiano con ruido se han visto comprometidas por nuestros descubrimientos acerca del HSP.