[ES] 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.
[ES] 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.
Desde que apareció la idea de utilizar computadores cuánticos para resolver problemas matemáticos de gran complejidad que no podrían ser resueltos en tiempo polinomial por computadores clásicos inició una carrera en la que compiten dos equipos: los que desarrollarán el primer computador cuántico de uso general y los que descubrirán como poder resistir al uso malicioso de estos nuevos computadores. La criptografía post-cuántica trata de imponerse a esta situación investigando nuevos algoritmos que reemplacen a los algoritmos actuales de clave pública como RSA dando lugar a sistemas resistentes tanto a algoritmos clásicos como a cuánticos antes de que la amenaza de un computador cuántico pueda acabar, entre otros peligros y en especial, con la seguridad y la privacidad en las comunicaciones a través de Internet. Se refleja en este proyecto el estado actual de la investigación en esta materia: algoritmos criptográficos basados en problemas que no pueden ser resueltos por computadores cuánticos, desarrollos y patentes, aplicaciones actuales y futuras, etc. dejando al lector una fuente de recursos óptima para su iniciación en la criptografía post-cuántica.
En un futuro cercano, la computación cuántica tendrá mucha influencia sobre la seguridad de las comunicaciones, con relevancia en entornos críticos como por ejemplo en defensa. Por esta razón cobra gran importancia plantear posibles soluciones como la criptografía cuántica y poscuántica. Surge entonces una pregunta; ¿Corre peligro la seguridad de las comunicaciones militares? Lo cierto es que con la cada vez más cercana llegada de la computación cuántica, la respuesta a esta pregunta es clara. Por ello es necesario anticiparse a la futura obsolescencia de los sistemas criptográficos actuales, sobre los que se sustenta toda la protección de datos clasificados y de operaciones estratégicas. En este Trabajo de Fin de Grado se exponen los fundamentos de la criptografía moderna para estudiar su evolución, las amenazas emergentes derivadas de la computación cuántica y las líneas de investigación que permitirán mantener la seguridad de las comunicaciones en defensa. El TFG se estructura en tres grandes bloques: criptografía clásica, cuántica y poscuántica. En primer lugar, se han tratado los principales algoritmos clásicos empleados actualmente, tanto simétricos como asimétricos, destacando sus vulnerabilidades frente a los algoritmos cuánticos de Shor y Grover. En segundo lugar, se ha analizado la criptografía cuántica (QKD), siendo una posible alternativa, cuya fortaleza se basa en leyes físicas. Sin embargo, aunque estos sistemas ofrecen un nivel de seguridad teóricamente inquebrantable, su implementación práctica sigue limitada por la necesidad de equipos específicos, la dependencia de autenticación clásica y los elevados costes de despliegue. Por último, se ha estudiado la criptografía poscuántica (PQC). Una gran alternativa, que propone algoritmos matemáticos resistentes a ataques cuánticos, con la ventaja de ser compatibles con la infraestructura existente. Además, se ha realizado una entrevista al experto Luis Fernando Hernández Encinas, cuyos resultados serán incluidos junto con la revisión bibliográfica en un análisis DAFO que permite identificar las fortalezas, debilidades, oportunidades y amenazas de ambas tecnologías. De este análisis se concluye que, la criptografía clásica se encuentra en fase de obsolescencia estratégica, mientras que la criptografía cuántica y la poscuántica representan los pilares de la seguridad futura. La primera ofrece una protección teórica total, aunque todavía no es viable a gran escala. La segunda, en cambio, constituye una solución práctica e inmediata para iniciar la transición.
Los avances en el campo de la computación cuántica obligan a desarrollar e implementar algoritmos criptográficos resistentes a ataques en ordenadores cuánticos (criptografía pos-cuántica) de forma urgente. La seguridad de los criptosistemas asimétricos actuales se basa en la dificultad de factorizar números enterosgrandes o resolver problemas de logaritmos discretos. Sin embargo, estos problemas matemáticos se puedenresolver en tiempo polinomial (eficientemente) usando ordenadores cuánticos. En respuesta, se realiza una intensa investigación sobre la criptografía pos-cuántica. Esta ciencia es el estudio de los esquemas criptográficos que serían seguros contra los adversarios que tienen computadoras cuánticas y clásicas y que a su vez pueden implementarse sin cambios drásticos en las redes y protocolos de comunicación existentes. Este artículo ofrece una descripción general del estado del arte de los esquemas asimétricos alternativos que tienen la capacidad de resistir ataques en ordenadores cuánticos y considera sus principales características.
Paradójicamente se vive una analogía entre las décadas de 1950s cuando se iniciaron los computadores que operaban con transistores y grandes máquinas que cubrían grandes espacios y la década de 2000s en la cual emergen nuevas hipótesis para optimizar el rendimiento del computador cuántico desde la algoritmia hasta los qubits y desde su composición hasta su comportamiento. Hoy en día se han mejorado diferentes aspectos relacionados al mundo cuántico donde se presentan retos como la criptografía, decoherencia, superposición de estados entre otros que son fundamentales para el alcance de este poderoso ordenador. Se han construido máquinas que factorizan pequeñas cifras, sin embargo persisten dificultades en cuanto a la lectura de la información ya que el mundo atómico es un inmenso océano el cual no se ha explorado lo suficiente, cuyas bases se mantienen en lo profundo de la metafísica. La idea general es que las personas interesadas en esta temática se ilustren un poco acerca de la tecnología que abarcará toda la información del futuro, generar inquietudes que motiven al descubrimiento e investigaciones que generen discernimientos a partir de la descripción que se realiza desde el origen de la computación cuántica, sus elementos y su comportamiento.
En esta tesis se presentan los resultados de una serie de experimentos opticos en los que se ejecutan algoritmos de comunicaciones cuanticas para realizar Distribucion Cuantica de Claves(DCC) criptograficas con estados coherentes de muy baja intensidad. Especificamente, se estudia la implementacion de esquemas practicos y robustos de DCC, con especial interes en sistemas basados en fibra optica. A diferencia de las comunicaciones por aire, este medio permite transmitir estados cuanticos con bajisimas atenuaciones y minimas perturbaciones externas, utilizando instrumental comercialmente disponible y de bajo costo, incluso para distancias de decenas de kilometros. Los protocolos de DCC estudiados codifican informacion clasica (bits) en estados cuanticos preparados sobre distintos grados de libertad discretos de sistemas fisicos. En el trabajo se exploran implementaciones que explotan la polarizacion y los modos temporales discretos de luz (time-bin). En ambos casos, fue necesario desarrollar y familiarizarse con tecnologias especificas para la preparacion, transmision y deteccion de dichos estados cuanticos. El problema de transmitir estados cuanticos en fibra de forma eficiente y robusta se ataco con dos estrategias. Por un lado, utilizando el grado de libertad de polarizacion y, por otro, modos temporales discretos de luz. En el primer caso, se codificaron los estados en el grado de libertad de polarizacion, que es facilmente accesible. Sin embargo, este es muy sensible a perturbaciones, por lo que para asegurar la robustez se incorporo un sistema de estabilizacion activa del Estado de Polarizacion(SOP, por su sigla en ingles). Con este esquema se implementaron dos variantes de un protocolo clasico de DCC, llamado BB84, utilizando la polarizacion de pulsos de luz para codificar los estados cuanticos. Esto requirio el desarrollo de una fuente de pulsos tenues de luz basada en un laser DFB en el rango de las telecomunicaciones, con un modulador de intensidad externo por electroabsorcion. Se diseno un sistema de estabilizacion de la polarizacion robusto que permite compensar de forma automatica las perturbaciones que genera la birrefringencia de la fibra sobre el estado de polarizacion. El sistema esta basado en controladores de polarizacion comerciales y electronica de control disenada especificamente, y puede ser adaptado facilmente a cualquier protocolo de comunicacion por fibra. En este sentido, se realizo una implementacion del protocolo BB84 y una variante llamada BB84E, que requiere la utilizacion de los seis estados de un conjunto completo de bases mutuamente no sesgadas para la polarizacion. En el segundo caso, se ensayo una codificacion mas sofisticada y resistente a perturbaciones, que implico enfrentar una serie de desafios tecnologicos, pero que se presenta como una alternativa practica y escalable en distancia de transmision y velocidad. Se propuso un esquema hibrido de DCC basado en un protocolo de referencia de fase distribuida con comunicacion bidireccional (Plug & Play), ambas tecnologias desarrolladas para trabajar especificamente en fibra optica, en un esquema con economia de recursos y distribucion tipo servidor-cliente. Asi, se obtuvo una configuracion en donde tanto el instrumental como las operaciones sobre los estados mas sensibles del protocolo se encuentran concentradas en una de las partes (servidor), mientras que los requerimientos sobre la otra parte involucrada en la comunicacion son minimos. Esta alternativa combina diferentes caracteristicas deseables en una implementacion practica de DCC, como la simplicidad y la robustez. El esquema propuesto codifica estados cuanticos en modos temporales discretos de luz. Esto requirio el desarrollo de dispositivos especificos para preparar y medir estos estados, basados en interferometros de fibra optica que no demanden estabilizacion activa. Otra de las premisas fue la independencia de funcionamiento del estado de polarizacion, que se logra a partir de la incorporacion de rotadores de Faraday en diferentes partes del esquema empleado. Por ultimo, debido al tipo de codificacion y al sistema de sincronizacion utilizados, este esquema es adaptable a tasas de transmision en el rango de los MHz. De los experimentos de DCC mencionados se desprenden una serie de desarrollos y pruebas de laboratorio adicionales, que son relevantes por si mismos. Entre ellos figuran la estabilizacion activa de interferometros de Mach-Zehnder en fibra y el estudio de esquemas experimentales alternativos para el protocolo hibrido de DCC propuesto. Tambien se puede destacar la puesta a punto de un prototipo autonomo de DCC en aire y su adaptacion para obtener un protocolo que distingue mezclas computables (pseudoaleatorias) de estados cuanticos. Este es un tema de interes para el procesamiento cuantico de la informacion en general. Las tecnicas abordadas y el know-how adquirido permiten entender y superar distintos problemas particulares de la utilizacion de estados cuanticos en comunicaciones por fibra optica. Ademas, estos desarrollos tienen la capacidad de ser empleados tanto en ensayos de DCC que excedan el ambito del laboratorio, como en un contexto mas amplio que permita implementar otros protocolos de comunicacion cuantica usando fibras opticas de telecomunicaciones como canal cuantico.
La criptografía surge para atender las necesidades de la sociedad de contar con una forma fiable de proteger la información en diferentes áreas, pero la criptografía clásica se revela progresivamente más insegura ante la evolución tecnológica de nuestra capacidad computacional. La criptografía cuántica, por el contrario, está basada en los principios de la mecánica cuántica y es capaz de proporcionar seguridad incondicional en las comunicaciones, independientemente de la capacidad tecnológica de un posible atacante. Dentro del campo de las telecomunicaciones, la mayor parte de los esfuerzos experimentales realizados en los últimos años con vistas a una realización comercial de la criptografía cuántica se han volcado en las redes de fibra óptica, donde además la luz es el sistema cuántico más fácilmente manipulable para implementar las técnicas criptográficas cuánticas. El primer sistema de criptografía cuántica, el denominado BB84, fue propuesto hace treinta años, y su principal inconveniente era que sólo podían garantizar seguridad a distancias de transmisión relativamente cortas (en torno a 25-30 Km). Para mejorar estas prestaciones, en los últimos años se han propuesto diversas variaciones, como los basados en el uso de "decoy states", en el que el transmisor emite pulsos luminosos de diversas intensidades que elige de manera aleatoria. Esta técnica permite estimar mejor el comportamiento del canal y posibilita transmitir claves criptográficas secretas a distancias cercanas a los 200 Km, aunque los grandes bloques de datos que debía procesar limitaban su máxima velocidad de reloj posible. Posteriormente, los protocolos de ¿fase distribuida¿ podían superar las limitaciones antes mencionadas, aunque su seguridad incondicional únicamente ha sido probada a medias distancias (inferiores a los 100 Km). El objetivo de esta tesis es precisamente estudiar la seguridad de estas técnicas y obtener cotas superiores para su distancia máxima de transmisión. Para ello, se evalúa en detalle la seguridad del protocolo COW ("coherent one-way"), que es empleado por la mayoría de los dispositivos de criptografía cuántica comerciales, mediante el estudio de ataques secuenciales contra este protocolo. Este tipo de ataques mantiene la coherencia en los bloques de pulsos luminosos reenviados, impiden establecer correlaciones cuánticas entre los usuarios legítimos del sistema y, por tanto, no permiten la distribución de claves criptográficas secretas entre ellos. Esta metodología permite demostrar, por primera vez, que gran parte de las implementaciones experimentales recientes del COW a largas distancias son inseguras. Los resultados de esta tesis también ponen en seria duda la viabilidad de estos protocolos para lograr distancias de transmisión similares a las obtenidas, por ejemplo, con el sistema basado en "decoy states".