Ya hemos explicado el potencial de las computadoras cuánticas para desafiar la seguridad actual de los servicios de red y las diversas soluciones que diferentes equipos están persiguiendo con el objetivo de integrar millones de qubits, con la finalidad de implementar algoritmos capaces de descifrar los métodos de cifrado actuales.
El desafío es enorme debido a las demandas físicas de los qubits, pero hay un amplio consenso en la comunidad cuántica de que en las próximas décadas veremos la materialización de una computadora cuántica.
En Telefónica, ya estamos inmersos en múltiples iniciativas destinadas a preparar nuestra red para garantizar su seguridad en todos los posibles escenarios futuros. Estamos realizando pruebas con redes cuánticas para proporcionar una alternativa físicamente segura para la distribución de claves. Asimismo, estamos experimentando con nuevos algoritmos de cifrado que podrían servir como complemento a los esquemas existentes. A continuación, os vamos a explicar la idea fundamental detrás de estos innovadores algoritmos de cifrado.
Selección de nuevos algoritmos de cifrado: los algoritmos post-cuánticos
El proceso de selección de nuevos algoritmos de cifrado sigue una competición abierta coordinada por el NIST (Instituto Nacional de Estándares y Tecnología), una agencia del Departamento de Comercio de los Estados Unidos.
Los algoritmos nuevos se denominan post-cuánticos, aunque no requieren un ordenador cuántico para su ejecución. Tal vez, un término más preciso sería «resistente al ordenador cuántico» o, en inglés, «quantum-proof», «quantum-safe» o «quantum-resistant».
En 2016, el NIST anunció la competición, y al final de 2017, un total de 69 algoritmos fueron seleccionados como candidatos para la primera ronda. En la segunda ronda, más de 40 algoritmos fueron descartados debido a problemas detectados en los estudios realizados por diversos equipos. De los candidatos iniciales, se seleccionaron 7 en 2020 para avanzar a la ronda 3. Se espera que el NIST concluya el proceso con una cuarta ronda, seleccionando finalmente los candidatos que serán estandarizados.
El avance del desarrollo de las computadoras cuánticas juega un papel crucial en este proceso. Dependiendo de dicho avance, el NIST puede optar por acelerar o retrasar el proceso de estandarización, e incluso podría abrir convocatorias adicionales para nuevas propuestas.
Requisitos para los algoritmos post-cuánticos
El algoritmo actual que facilita intercambio de información se fundamenta en esquemas donde la seguridad está estrechamente ligada a la dificultad que presentan los ordenadores actuales para factorizar números grandes en dos números primos.
La existencia de un algoritmo cuántico conocido, Shor, capaz de resolver el problema de factorización, implica que los esquemas actuales ya no son seguros cuando se dispone de un ordenador cuántico lo suficientemente potente. Los nuevos algoritmos que están siendo evaluados se basan en problemas matemáticos novedosos para los cuales no se conoce ningún método, ya sea en ordenadores cuánticos o clásicos, que permita resolverlos.
Es crucial comprender que cualquier esquema de cifrado se basa en el desconocimiento de un algoritmo para resolver el problema fundamental. Esta condición no implica que no haya una solución en el futuro. De hecho, muchos algoritmos propuestos en el proceso del NIST fueron descartados debido al descubrimiento de nuevos algoritmos capaces de romperlos. Un ejemplo destacado es el caso de SIKE, desarrollado en colaboración entre ingenieros de Amazon, Microsoft y la Universidad de Versalles. SIKE avanzó hasta la ronda 3, pero fue desestimado cuando se identificó un algoritmo que podía romperlo utilizando un ordenador portátil convencional en cuestión de horas. Este ejemplo subraya la naturaleza dinámica y en constante evolución del campo de la criptografía.
Retículo: la nueva promesa del problema imposible
Cinco de los siete algoritmos seleccionados por el NIST pertenecen a la categoría de retículo. Similar al problema de factorización en números primos, los problemas en retículo están emergiendo como la nueva esperanza para los sistemas de cifrado resistentes a los ordenadores cuánticos.
Para comprender este concepto, imagina tener una hoja de papel en blanco que deseas llenar con puntos. Sin embargo, hay una limitación: solo puedes moverte entre puntos utilizando dos patrones posibles, ya sea en dirección vertical o en dirección horizontal. Por ejemplo, si deseas llegar al punto (8-1) desde el punto central (5-5), necesitarías realizar 4 movimientos hacia arribal y 3 movimientos hacia la derecha.
Es sencillo visualizar que mediante combinaciones de estos movimientos, solo se pueden alcanzar los puntos de intersección en la imagen. Los vectores azul y negro se denominan la «base», y todos los puntos accesibles mediante la combinación de esta base se conocen como retículo.
Un mismo retículo puede ser generado por múltiples bases. Por ejemplo, otra base podría estar representada por los vectores marcados en negro y azul, en la siguiente figura. En este caso, llegar al punto 8-1 implicaría realizar 2 movimientos azules, restar 2 movimientos negros, 4 movimientos azules y finalmente, 1 movimiento de color negro. Aunque la base difiere de la anterior , ambas bases permiten llegar a los mismos puntos. En otras palabras, la base genera el mismo retículo que la base.
Es importante destacar que la facilidad para llegar al punto 8-1 varía significativamente dependiendo de la base utilizada. Mientras que es relativamente fácil generar el camino con la base (imagen 1), resulta más complicado hacerlo a partir de la base (imagen 2). Esta distinción entre bases simples y complicadas es una característica fundamental que se aprovecha en la construcción de muchos de los nuevos algoritmos para el intercambio de información.
Una idea concreta sería la siguiente: Imagina que mantienes en privado la base fácil y compartes la base difícil de manera pública para que otros puedan enviarte información. Un posible algoritmo podría seguir este proceso:
En el primer paso, la persona generaría un camino aleatorio utilizando la base pública (negro y azul) para cada bit de información. En la figura, observamos que el primer camino llega a la coordenada 7-2 y el segundo a la 6-3. En el segundo paso, la persona te enviaría las coordenadas, introduciendo una pequeña variación dependiendo de si la información a enviar es 0 o 1. Por ejemplo, podría sumar un valor pequeño aleatorio si desea enviar 0 y restar un valor pequeño si desea enviar 1. En este caso, podría enviarte las coordenadas 7.1-2.1 y 5.8-2.8, respectivamente.
Cuando recibes información, el único paso necesario es buscar el punto más cercano en el retículo utilizando la base fácil. Calcular que el punto más cercano a 7.1-2.1 es 7-2 con la base azul y roja sería computacionalmente sencillo. A partir de ahí, puedes determinar si te están enviando un 0 o un 1. Este proceso de descifrado es simple si dispones de la base adecuada. En contraste, sería extremadamente complicado en el caso contrario. Por ejemplo, si un hacker intercepta la coordenada 7.1-2.1, tendría que generar todos los puntos posibles alrededor de este punto con la base complicada y luego seleccionar el punto más cercano. Computacionalmente, este proceso es muy costoso, especialmente cuando el número de dimensiones es elevado.
No se conoce un algoritmo eficiente para llevar a cabo la “búsqueda de puntos cercanos” en un retículo en computadoras clásicas ni cuánticas. Muchos de los algoritmos seleccionados por el NIST se fundamentan en este problema. Estrictamente hablando, se basa en el problema de «learning with errors» (aprendizaje con errores), o sus variaciones, que está relacionado con el problema de la búsqueda de puntos cercanos en retículo.
Ya hemos examinado cómo un ordenador cuántico suficientemente grande podría comprometer la seguridad actual de Internet y hemos explorado los diversos diseños de qubits que los equipos pioneros están persiguiendo en busca de este logro. Mientras tanto, organismos ya están trabajando en tecnologías para preparar la red del futuro, estableciendo nuevos estándares de algoritmos de cifrado resistentes a los ordenadores cuánticos.
