Cloudflare TV

🔒 Las siete vidas de un gato post-cuántico

Presented by Armando Faz, Sofía Celi
Originally aired on 

Cloudflare Research presenta un panorama de la Criptografía Post-Cuántica. Esta es una de las áreas más novedosas en criptografía y trata sobre la creación de algoritmos resistentes al cómputo cuántico. Nuestros investigadores, Sofía y Armando, presentarán el estado actual del área. Incluyendo los algoritmos propuestos, el trayecto rumbo a su estandarización y su aplicación en protocolos de comunicación.

Spanish
Privacy Week

Transcript (Beta)

Hola a todas las personas y bienvenidos a esta charla sobre criptografía poscuántica que va a ser en español y estoy muy feliz aquí de estar con Armando y por favor las diapositivas.

Bienvenidos. Hola que tal Sofía, mi nombre es Armando. Mientras les comparto las diapositivas, les damos la bienvenida a esta sesión de Cloudflare TV y el día de hoy vamos a hablar sobre computación poscuántica.

Bien, un poquito acerca de los presentadores, Sofía.

Muchas gracias Armando. Mi nombre es Sofía Celi y soy una investigadora en el equipo de criptografía de Cloudflare y especialmente me dedico ahora a experimentos con criptografía poscuántica que es justamente el tema de la charla.

Armando por favor. Sí, mi nombre es Armando, Armando Faz. Me gusta trabajar en la implementación eficiente de criptografía y ahora vamos a discutir un poquito sobre la criptografía poscuántica.

Bien, mucho se ha pensado a lo largo del tiempo cuál es el poder de cómputo que se puede llegar a lograr.

Con las computadoras como las conocemos ahora se han podido resolver bastantes problemas que tenemos en la vida cotidiana.

Sin embargo, muchas personas han pensado, bueno, ¿cuál es el siguiente paso que tenemos con respecto ahora?

Y está uno de estos grandes pensadores que tenemos contemporáneos, Richard Feynman, que cerca de la década de los ochentas, bueno, él es físico, él se preguntaba, bueno, ¿será que existe un modelo de computación que sea aún más poderoso que el modelo que conocemos?

Bueno, que se conocía en ese entonces y que ahora, bueno, conocemos como un modelo clásico de computación, pero con la variante de que este modelo de computación obedezca las leyes de la mecánica cuántica.

Y bueno, esta idea, primero él se conjeturó si realmente era esto posible.

Y bueno, desde entonces los físicos y gente que analiza la teoría de la computación ha visto formas de cómo utilizar estos recursos de la mecánica cuántica.

Bueno. Y quizás ahí añadir una de las razones por las que se quería crear ahora una máquina que siga las leyes, obedeciera las leyes de la mecánica cuántica, era precisamente para poder correr experimentos que intentaban demostrar ciertas características de la física cuántica que no podían ser corridos en computadoras clásicas.

Así es que así todo comenzó en el tema del que estamos hablando.

Bien, entonces una de las propiedades de la computación cuántica con respecto a la computación clásica es el conocido principio de superposición.

Este principio, aquí lo quiero resumir por ejemplo con esta figura que va a ser una forma fácil de entenderlo, es cuando uno tiene los bits clásicos, uno empieza a hablar de esta dualidad entre 0 y 1, que representa dos estados, prendido y apagado, arriba y abajo, izquierda y derecha.

Y esta es como la unidad, esta es la unidad fundamental de información que tenemos en un esquema de computación clásica.

Sin embargo, cuando entramos a la computación cuántica, tenemos estados en la materia los cuales pueden estar en superposición.

¿Qué quiere decir esto? Que hay un estado que al determinado momento puede representar una gran cantidad de estados.

En este caso, por ejemplo, en la figura vemos un selector, por ejemplo, en el cual un qubit nos viene a representar todos los estados desde prendido hasta apagado, pero también todos los estados intermedios que hay entre estos dos estados.

A esto se le va a conocer como qubit o bit cuántico, y bueno, es uno de los principios fundamentales de la computación cuántica.

El segundo principio es la medición.

Tenemos estados en la materia, en los cuales este, recuerden, este principio de superposición es un estado, representa varios niveles o varios valores al mismo tiempo.

Sin embargo, una vez que nosotros observamos el sistema, o medimos, o tratamos de saber cuál es aquel valor que está en un determinado momento, a eso le vamos a llamar medición.

Entonces, una vez que medimos el estado, sabemos en qué estado se encuentra, pero causa un efecto muy particular, que es que en ese momento el estado ya no está más en un estado cuántico y tiende a ir hacia uno de los estados clásicos.

Entonces, es como si al empezar a ver en qué estado se encuentra, el qubit se decanta, ya sea hacia el 1 o hacia el 0, y a partir de ese momento ya no tenemos un estado cuántico.

Y quizás, Armando, podrías hablar un poco acerca del ejemplo de lanzar una moneda, que es uno de los más representativos sobre esto.

Ya, efectivamente. Nosotros, por ejemplo, tenemos el experimento de lanzar una moneda, suponemos que la moneda no está cargada hacia ningún lado.

Al momento de lanzar una moneda y ver que azota en el suelo, nosotros podemos decir, bueno, cayó en cierto lado de la cara.

Pero aquel momento en el que la moneda está rodando en el aire, eso podría llegar a verse como una simplificación de lo que es un qubit.

Es decir, en ese momento no tenemos certeza de cuál va a ser el resultado final del valor de la moneda, de cuál cara es la que cae viendo hacia el suelo, ¿cierto?

Y solo tenemos certeza hasta el momento en el que la moneda cae y se detiene su movimiento.

Entonces, esto del qubit permite expresar varios valores con una cierta probabilidad, porque en ese momento no tenemos una forma de saber cuál va a ser el estado.

Solo tenemos probabilidades.

Puede ser que caiga de un lado o puede ser que caiga del otro, con cierta probabilidad.

Bueno, el entrelazamiento.

Este es una propiedad muy interesante del cómputo cuántico, que es al momento de que tú mides o que uno mide cuál es el estado de un qubit, existió en los experimentos que notaron que había cierta interferencia entre el estado de otro qubit.

Es decir, al momento de que uno mide un qubit, el valor de un qubit, algo pasa que pasa una reacción del otro lado, que puede ser a cierta distancia, inclusive a una distancia larga, y el estado de otro qubit se afecta.

Esto se conoce también como la paradoja de Einstein, Rosen y Podolsky, la paradoja IPR, que en aquel tiempo se preguntaban, bueno, ¿qué es lo que está pasando?

¿Cómo es posible que yo mida en este punto este estado e inmediatamente pasa otra cosa en otro estado?

Y una forma de explicarse esto de forma irónica era que, bueno, ¿acaso está ocurriendo un intercambio mágico de información ahí?

Y bueno, esto también puede servir para realizar un protocolo de comunicación.

Bueno, si tenemos esta forma de, digámoslo así, comunicar bits o comunicar un cierto tipo de información, entonces se pueden crear protocolos para, actualmente hay dos protocolos bien conocidos, que es el envío de dos bits clásicos de información, o el envío de un estado cuántico de un punto a otro, que también a veces se le conoce como teletransporte cuántico.

¿Y sabes si este segundo experimento del envío de un estado cuántico es usado en la vida real ahora?

Es difícil porque se tiene que mantener el estado, ¿no? Primero, yéndonos a lo básico, es primero mantener el estado y después tratar de poder enviarlo.

Pero por lo menos la construcción teórica es posible.

Y bueno, la parte de la puesta en práctica es un tema completamente diferente.

Bien, entonces, dado este poder cuántico, ¿qué es lo que se puede hacer?

¿Sophie, si te gusta hablar un poquito de eso?

Sí, entonces, una de las cosas que se comenzó a pensar es si es que existen estas computadoras cuánticas, ¿se puede utilizar los poderes que nos da la mecánica cuántica para tratar de resolver ciertos problemas matemáticos de forma mucho más rápida?

Y de esta forma ya comenzamos en la presentación a ligarnos hacia lo que es la criptografía, porque estos dos algoritmos de los que vamos a hablar a continuación están ligados hacia cómo la criptografía funciona.

El primero de ellos es el algoritmo cuántico de Shor, y básicamente este algoritmo es devastador para la criptografía porque la criptografía que utilizamos ahora está basada sobre ciertos problemas matemáticos.

Básicamente la criptografía que más usamos el día de hoy es la criptografía de curvas elípticas y la criptografía RCA, que están basadas en el problema del logaritmo discreto y en el problema de la factorización de enteros.

Dichos problemas matemáticos no es que son imposibles de resolver, sino que toma mucho tiempo para las computadoras actuales resolver dicho problema si se utilizan números realmente grandes.

Pero lo que encontró Shor fue que al utilizar las técnicas de la mecánica cuántica se puede resolver mucho más fácilmente la factorización de enteros, lo que significa que se quiebran los sistemas como RCA y puede ser también extendido para resolver el problema del logaritmo discreto, lo que significa que también las curvas elípticas que nosotros utilizamos van a ser rotas.

No sé si quieres agregar algo, Armando.

Bueno, este realmente es uno de los algoritmos más devastadores, por decirlo así, en cuanto a la criptografía que conocemos.

Bueno, vamos a saltar un poco al siguiente algoritmo, que es el algoritmo de Grover.

En este caso, este también es un algoritmo cuántico, es un algoritmo de búsqueda.

Este es un poco diferente, en el cual se necesita encontrar la primagen de una función, es decir, aquel elemento que al aplicar la función obtienes una salida.

Este algoritmo utiliza bastante lo que es la superposición de estados, o toma ventaja de ello.

En este caso, supongamos que tenemos una función binaria en entradas y que te arroja un bit.

Si quisiéramos hacer la búsqueda de forma clásica, bueno, si tenemos en entradas binarias, tenemos dos a la n posibles estados.

Y si quisiéramos buscar cuál es aquella entrada que produce la salida que yo quiero, tendríamos que buscar, si lo hiciéramos por fuerza bruta, pues dos a la n intentos.

Sin embargo, con el paralelismo cuántico y este algoritmo de Grover, podemos reducir por la mitad en la parte del exponente, o el número de intentos.

En la pantalla pueden ver una pequeña animación de cómo funcionaría el algoritmo de Grover.

Imagínense por un momento que en la línea horizontal yo pongo todas las dos a la n posibilidades.

En estas dos a la n, yo sé que alguna de ellas es la respuesta.

Lo que hace el algoritmo de Grover es que iterativamente va haciendo que la respuesta salga a la luz.

Imagínense, por ejemplo, como si tuviera una pequeña caja donde tengo arena, arena de esta muy fina, y al tratar yo de mover o de sacudir esta caja, aquellas partículas que son un poco más pesadas o más ligeras, ellas van a variar en cuanto al peso y se van a mover diferente.

Algo similar está pasando aquí. Al yo hacer operaciones sobre este estado en superposición, aquel valor que es realmente la respuesta, su probabilidad se va a incrementar y va a tender a la hora que yo sacudo, va a salir automáticamente.

En este caso, por ejemplo, vemos que la respuesta que está por ahí, al momento de sacudir, como se puede ver, va creciendo, va creciendo su probabilidad.

Aquí la probabilidad está entre 0 y 1.

Y al ejecutar el algoritmo, su probabilidad va creciendo, dado que el momento que yo termino y finalizo con una medición, entonces tengo una probabilidad del 100%, una probabilidad de 1, de haber encontrado la respuesta.

Bien, entonces, dados.

Ahí existen muchos más algoritmos, pero dados para criptografía son los más importantes.

Sophie, ¿nos puedes contar un poquito eso? Sí, entonces aquí es más o menos para darles un poco una línea del tiempo sobre cómo todo ha sucedido en cuanto a la criptografía poscuántica.

Y en general, también acerca de las computadoras cuánticas en sí mismas.

La primera cuestión es que, como vimos, la primera idea de la computadora cuántica ya vino hace mucho tiempo acerca de Richard Feynman, y tanto el algoritmo de Grover fueron desarrollados mucho antes, en 1995, me parece.

Durante todo ese tiempo, hasta el 2015, hubo muchos criptógrafos que expresaron sus preocupaciones acerca de que ya venían estos algoritmos cuánticos, que ya venían estas computadoras cuánticas que iban a romper la criptografía como es conocida ahora.

Pero no fue hasta el 2015 que la NSA, que es la Agencia de Seguridad estadounidense, expresó la necesidad de tener una criptografía que sea poscuántica.

Y esto fue uno de los primeros momentos en que realmente los organismos mundiales comenzaron a tomar en cuenta lo que era la criptografía poscuántica.

A partir de eso, en el 2016, NIST, que es el organismo, el Instituto de Estandarización, convocó a propuestas para estandarización de criptografía poscuántica, en dos áreas especialmente, para encriptación y para crear firmas digitales.

Pero sin embargo, una cuestión que todavía se discute hasta el día de hoy, a pesar de que hay un esfuerzo de generar la estandarización, es si es que es todavía necesario.

Porque todavía no hay un entendimiento de realmente cuándo las computadoras cuánticas van a venir, si es que realmente van a venir, si es que va a ser posible realmente construir computadoras cuánticas.

En el momento actual parece que sí va a ser posible construir realmente computadoras cuánticas eficientes, pero todavía no se sabe exactamente cuándo, puede ser mañana, como puede ser en 100 años.

Entonces, una de las preocupaciones que también la comunidad de criptografía actualmente tiene, es que no deberíamos esperar hasta que dichas computadoras cuánticas aparezcan, sino desde este momento deberíamos ser precavidos y comenzar a crear algoritmos poscuánticos, para que cuando lleguen las computadoras cuánticas no rompan todos los sistemas que utilizamos, sino que ya tengamos un reemplazo inmediatamente.

¿Algo más, Armando?

Así es. Sí, lo has dicho bien. Debe haber una cierta preparación en vista pensando hacia el futuro.

Sobre todo, por ejemplo, ahora todos usamos criptografía clásica, pero si yo colecciono o recopilo cierta información que está cifrada con cifradores actuales, que pueden ser quebrados con un modelo de computación cuántica, quizás lo que yo colecte ahora quizás lo pueda descifrar en el futuro.

Es por eso que es importante tener o estar precavidos ante una posible venida de estos computadores.

Bueno, aquí hay un timeline sobre la computación cuántica.

¿Sophie, quieres comentarnos un poquito?

Sí. Esto solamente es una línea del tiempo, como más tener una idea de cómo sucedió.

Como les conté, recién en el 2015 es que la NSA y NIST en 2016 comienzan a pensar que realmente necesitamos estandarizar los algoritmos poscuánticos.

Pero como vemos y como Armando ya ha dicho, en 1994 se publicó el algoritmo de Shor, del que ya hablamos.

En 1996 se publicó el algoritmo de Grover, del que hablamos también.

Y desde entonces ya se comienzan esfuerzos a tratar de construir computadoras cuánticas que sean estables, donde se puedan realizar estos algoritmos.

Y por ejemplo en el 2001 ya el número 15 es factorizado.

¿Qué significa esto? No significa que alguien realmente ahora en el mundo real factorizó el número 15, porque cualquier persona puede factorizar el número 15.

Lo que significa es que una computadora logró factorizar el número 15. En el 2005 el QBIT, del que habló Armando, es anunciado como realmente, como ahora existe este parámetro que se llama QBIT, más o menos representa 8 QBIT, perdón, un QBIT, 8 QBIT, más o menos.

En el 2002 el número 21 es factorizado. Y desde el 2017 ciertas compañías han comenzado a invertir bastante en la creación de computadoras cuánticas, como es IBM, como es Google.

Al mismo tiempo otras organizaciones y otras compañías comenzaron a lanzar experimentos para medir qué tan fácil o qué tan difícil sería incluir algoritmos poscuánticos en, por ejemplo, TLS o en otro tipo de protocolos criptográficos que existen.

Así es.

Bien, vamos a pasar a... ¿Será que esto realmente es un problema? Es una pregunta que hemos escuchado bastante en el ámbito.

¿Será que realmente tenemos un problema con la llegada de los computadores cuánticos?

Sí, no se puede saber realmente si es que tendremos este problema porque ahorita no tenemos computadoras cuánticas.

Tampoco sabemos si es que se van a desarrollar nuevos algoritmos cuánticos que rompan otros problemas matemáticos sobre los que los nuevos algoritmos están basados.

Hay mucha incertidumbre, pero la idea en la comunidad criptográfica es que ya que no sabemos si tenemos tiempo, ya que no sabemos cuánto tiempo tenemos, lo mejor es tratar de cambiarlo ya y hacer un proceso de estandarización que sea bueno, que sea estable, para saber si es que lo que proponemos ahora va a servir en un mundo donde haya computadoras cuánticas.

Entonces es mejor estar preparado, ¿cierto?

Sí. Ok. Bueno, ¿pero qué alternativas tenemos?

Las alternativas que tenemos yo podría decir tres alternativas. La primera es utilizar los mismos cifrados que utilizamos en llaves simétricas, pero aumentar el tamaño de las llaves.

Y esto se corresponde con lo que estaba diciendo, que los problemas matemáticos sobre los que está basada la criptografía actual no es que son imposibles de resolver, sino que muchas veces utilizan números demasiado grandes para poder resolverlos en un tiempo eficiente.

Si es que utilizamos números más grandes, obviamente una computadora va a tener que demorarse más tiempo en resolverlos.

¿Pero cuál es el problema si utilizamos algoritmos con un tamaño de llaves gigantesco?

¿Qué es terabytes, por ejemplo? ¿Qué la transmisión de dichas llaves a través de una red va a ser imposible?

Porque tenemos que tener redes muy, muy eficientes y una actividad muy, muy eficiente en el mundo para poder funcionar con eso.

Entonces, opción no es muy viable. Hay otros algoritmos que utilizamos en la actualidad, como por ejemplo los hashes, que sí sobreviven a un modelo cuántico de la computación, porque el problema sobre el que están basados no es atacado por computadoras cuánticas.

Y de hecho, una de las propuestas para utilizar en el mundo cuántico es un algoritmo que se llama XMSS, que no fue estandarizado por NIST, fue estandarizado como un RFC, a la par incluso de la competición de NIST.

Y ni siquiera entró en la competencia, sino que fue estandarizado por sí mismo, porque sabíamos que el problema matemático sobre el que se basa iba a sobrevivir, va a sobrevivir en un mundo cuántico.

Un mundo que tiene computadoras cuánticas, porque el mundo ya es cuántico.

Sí, efectivamente. Sí, la mecánica cuántica está en la naturaleza. El punto es saber aprovechar esa naturaleza para crear computación.

Bien, bueno, esto es acerca de cifrado simétrico.

¿Qué pasa con la parte simétrica?

Recordemos que, como ya hemos dicho, tanto el algoritmo de Shor aplica al quiebre de RCA o de curvas elípticas.

Entonces, bueno, tenemos que buscar alternativas que nos permitan tener de nuevo criptosistemas de llave pública confiables.

Y bueno, este tema es algo que se le conoce como criptografía poscuántica, o criptografía que es resistente al uso de computación cuántica.

Y bueno, aquí hay varias opciones en las cuales, bueno, afortunadamente hay varias opciones, no hay solo una, en las cuales se puede trazar el rumbo hacia dónde vamos para los próximos años.

Bueno, aquí enumero las categorías de las opciones más prometedoras.

Tenemos lo que es las redes, usando látices o reticulados. Tenemos otro tipo de criptografía que se basa en la teoría de códigos.

Uno más que es el sistema de ecuaciones cuadráticas no lineales.

Uno mucho más reciente que es el cálculo de isogenías entre curvas elípticas.

Que este es un problema diferente al problema del logaritmo discreto, solo para mencionar.

Y bueno, como ya mencionó Sophie, el problema de calcular firmas digitales pero usando hashes.

Y bueno, tenemos por ejemplo el algoritmo XMSS que ya lo mencionó Sophie.

Entonces, ante este número de opciones, ¿qué es lo que sigue Sophie?

Lo que sigue es describir cada uno. Bueno, vamos. Entonces, empezamos con los basados en código.

En este caso, en la teoría de códigos, hace algunos años fue muy reconocida por crear códigos que permitan la corrección de errores al enviar información entre dos puntos.

Mucha gente se lanzó a tratar de estudiar este problema.

Y bueno, ya desde tiempos atrás este era un problema conocido. Enviar información de manera confiable y poder recuperar errores en la transmisión si es que lo sabían.

Entonces, está este algoritmo propuesto por Mike McKellis en la década de los 70's.

En el cual, bueno, es un código que tiene la complejidad de encontrar...

Estos códigos están generados por una matriz generadora.

Y bueno, el problema difícil es encontrar esta matriz, ¿cierto?

Un punto en contra que tienen los criptosistemas basados en códigos es que el tamaño de llaves es extremadamente grande.

En principal porque tanto el código tiene que cargar la información de la llave por sí misma o de la información por sí misma.

Pero también tiene que cargar un pedazo extra de información que es el que le permita recuperar o detectar si hubo errores o no durante la transmisión.

Entonces, este criptosistema, sí, es uno de los más antiguos que es resistente a post-quantum.

Y que bien se estudió hace algún tiempo, ahora está tomando una relevancia de nuevo por tener esta propiedad.

¿Sophie nos comenta sobre Lattice?

Sí. Entonces, otro de los problemas que se piensa utilizar como parte de algoritmos que sea que funcione en un mundo donde hay todas las cuanticas es el problema de si utilizamos redes, Lattice en inglés, para firmas, que puede servir tanto para firmas digitales como en criptación.

Primero es bueno notar que ciertos de esos problemas que estamos describiendo pueden ser aplicables para cifrado, en criptación.

Otros pueden ser aplicados para firmas y algunos pueden ser aplicados para los dos.

Pero algunos solo pueden ser aplicados para uno de ellos.

Entonces, los basados en una red fue primero propuesto por tres investigadores, por Hobson, Piper y Silverman, un sistema que ellos nombraron Entru.

Y básicamente funciona casi de la misma forma de la forma que fue descrita el sistema basado en códigos, en el sentido de que un punto se esconde, se encripta en una red, pero en vez de cambiar ciertas coordinadas, se cambia todas las coordinadas.

Este es uno de los sistemas que más apoyo ha tenido e incluso de los finalistas de la tercera fase de NIST, la mayoría están basados en este problema.

Entonces, una de las cosas que se puede decir ahorita a futuro es que quizás este es el sistema que va a ser utilizado en el futuro.

Entonces, si quieres agregar algo.

Sí, bueno, en su parte Entru, como bien lo dijo Sofía, es también bastante conocido, bastante estudiado.

Una variante que utiliza un problema parecido es el aprendizaje con errores, o RWE, en el cual usan la R por ring, anillo.

Básicamente son utilizar polinomios sobre un cuerpo finito, esto genera lo que es un anillo, una estructura algebraica, y de estos polinomios, que son los ciudadanos de este universo, se les define un concepto de norma, entonces podemos diferenciar, usando esta norma, cuáles son polinomios que son pequeñitos con respecto a polinomios grandes, dependiendo de esta norma.

Y bueno, eso nos permite que podamos, a nuestro texto cifrado, poderle agregar errores, errores que son pequeñitos suficientes, que al momento de tomar la norma, este error se puede desaparecer.

Entonces, al agregar este error, nosotros escondemos la información, y al tomar la norma, nos deshacemos del error.

Un punto importante, por ejemplo, en este tipo de criptografía, es que la generación de polinomios necesita un generador de números con una distribución gaussiana, lo cual es algo diferente, y también es un problema que se está estudiando bastante.

Porque normalmente, en sistemas clásicos, sistemas comunes, lo que queremos es una distribución uniforme, donde, bueno, dada todos los elementos de un conjunto, queremos recuperar a alguno con la misma probabilidad de haber escogido uno u otro.

La distribución gaussiana, recuerdan, es esta forma de campana, y bueno, algunos tendrán mucha más probabilidad de ser escogidos que otros.

Entonces, bueno, este es un buen punto a tomar en cuenta. Ahora, tenemos las isogenías.

Bueno, este es un problema un poco más nuevo, más reciente, que es encontrar una conexión matemática entre dos curvas elípticas de determinado tamaño.

Este problema, como mencioné, es diferente al problema del logaritmo discreto, en el cual uno necesita encontrar un elemento que genera a otro punto en una curva.

Entonces, bueno, el usar isogenías hereda bastante del uso de curvas, que es el menor tamaño de llave posible.

Entre los candidatos que existen, su rendimiento, bueno, hay algunas fuentes que dicen que es equiparable al rendimiento de RCA para tamaños grandes de llaves.

Pero si se compara, por ejemplo, con el uso de redes o látices, es bastante lento, porque los látices son bastante rápidos.

De este tenemos algunas variantes, como lo es Psyche, que es un sistema de encapsulamiento de llaves.

Tenemos otro más reciente, que es SysAid, que es una encapsulación de llaves, pero permite validar llaves públicas.

Y bueno, uno muy muy reciente, que en este mes fue publicado, que es SQI Sign, que es un esquema de firmas digitales usando isogenías.

Pero aún estos esquemas se quedan un poco atrás en cuanto a la cantidad de computador que es necesaria para ejecutarse.

Quizás ahí podemos también añadir que una de las cosas que tenemos en la criptografía actual es que existe este sistema que se llama el protocolo de Higelman, que todo el mundo ama por su simplicidad.

Todos los otros algoritmos que hemos visto, en la forma en que por el momento han sido diseñados, no se equiparan en la misma simplicidad.

Pero con estos, especialmente con las isogenías, hay una forma de tratar de hacer la misma simplicidad de Diffie -Hellman, con un algoritmo poscuantio.

Los algoritmos que están basados en hash, que un poco ya lo hablamos, básicamente el problema sobre el que están basados es que encontrar la imagen de un hash es difícil.

Es decir, si a ti te dan el hash, encontrar el texto sobre el que fue generado es una cuestión difícil.

Básicamente estos algoritmos son exactamente igual a cómo funcionan hoy los hashes.

La única diferencia es que al momento en que se genera hash también hay que cambiar un estado.

Entonces hay que tener en cuenta siempre el estado que uno tiene que cambiar.

Esto al menos en el caso de XMSS, pero en el caso de por ejemplo Sphinx, no es necesario mantener el estado.

Este algoritmo solamente va a funcionar para firmas digitales y probablemente va a ser el que yo pienso al menos que va a ser más utilizado por su simplicidad también, pero solamente es aplicable a firmas digitales.

Así es. Bien, vamos a pasar ahora a... Ah bueno, nos falta uno.

Las ecuaciones... Y este, que es de los basados en ecuaciones multivariantes cuadráticas, es tanto para encriptación y firmas.

Es el que parece más complejo, pero de hecho, a excepción del basado en hashes, es uno de los basados, el uno que puede decir el más simple de entender en relación a los otros problemas matemáticos.

Fue propuesto por primera vez en 1998 por Matsumoto, pero fue roto y un nuevo sistema fue creado.

Y básicamente la idea es que utiliza sistemas de ecuaciones cuadráticas en varias variables, n variables y m ecuaciones.

¿Y cuál es el problema? Es encontrar una solución para todas ellas. ¿Cuál es el problema en usar este sistema?

Que el tamaño de las aves es kilobytes, entonces no representa una buena viabilidad.

De todas maneras, uno de los finalistas de hecho de la competición utiliza ese sistema, así que es bueno tenerlo en cuenta.

Pero vamos a ver luego que de hecho hay un pequeño ataque ahí. Uy.

Bien, ahora sí, tenemos este slide, vamos a mover un poco a lo que es el NIST y la competición actual.

Bien, tenemos aquí actualmente, bueno, ya desde 2016 que se inició esta competición, para tratar de encontrar cuáles serían los algoritmos que sean aplicables o que tengan un uso en nuestro mundo actual, en vista de estar preparados ante la llegada del cómputo cuántico.

Hay dos categorías principales, la cual es ya sea el cifrado o el encapsulamiento de llaves y las firmas digitales.

Estos dos servicios principalmente son los principales usados al momento de realizar conexiones seguras con un servidor.

Por ejemplo, en el caso de TLS, cuando quieres entrar a una página web de forma segura, estos dos primitivos son los principales que tienes que tener.

En cuanto al cifrado y encapsulamiento de llaves, ahora hay cuatro finalistas, que son los que están, digamos, actualmente en una de las últimas fases de la competición.

Como ya mencionamos, el criptosistema MacElise, basado en códigos, Kyber, Entro y Saber, todos ellos están basados en redes, permiten encapsulamiento y cifrado de información.

Y del lado de las firmas hay, en este caso, tres contendientes, que es Dilithium y Falcon, que son basados en redes también, y Rainbow, que está basado en ecuaciones cuadráticas.

Bien, entonces, dados estos siete candidatos, la idea es, bueno, ya están estos, ahora tratar de ver cómo integrar estos en aplicaciones reales.

Bueno, algo importante para mencionar es el tamaño de las llaves.

En esta tabla, bueno, sumarizamos lo que son los algoritmos y el tamaño de las llaves públicas y de las firmas, por ejemplo.

Y, bueno, en este caso, para que ustedes tengan un contraste en cuanto a lo que es actual, que es, por ejemplo, las firmas usando RCA o usando curvas elípticas, que son los dos primeros renglones, si ven, el tamaño de las llaves es ronda o no va más allá de cientos de bytes, o sea, son realmente pequeños.

Pero cuando vamos a estos nuevos esquemas postcuánticos, vemos que el tamaño de llaves se incrementa bastante en algunos casos, ya sea que el tamaño de llaves es muy alto o que las firmas digitales son más grandes.

Bien, entonces, bueno, esta pequeña sutileza se vuelve importante al momento de aplicarlo en el desarrollo de conexiones seguras.

Bien, ¿qué nos puedes comentar aquí, Sofía?

Entonces, el hecho de que ahorita NIST haya resolvido que hay ciertos siete algoritmos que quizás puedan ser utilizados para un mundo donde hay computadoras cuánticas, no significa que ya no haya inseguridades, porque la competición todavía sigue en curso.

Y, de hecho, creo que este mes o hace un mes, se publicó un paper sobre un ataque a uno de los algoritmos de los que hablamos, que es el algoritmo Rainbow, que está basado sobre ecuaciones cuadráticas.

¿Cuál es el ataque? Básicamente está basado en una idea anterior por otros investigadores, por Shamir, me parece, y básicamente lo que dice es que, como sabemos, el sistema de Rainbow está basado en un sistema que tiene ecuaciones y variables.

Cuando las variables son dos veces el número de las ecuaciones, hay una forma de romperlo.

Si es que se cambia el parámetro a algo que no es seguro, entonces hay formas de romperlo, que es uno de los puntos importantes al hablar de la estandarización de NIST, que los parámetros, cómo escoger los parámetros, a veces todavía no hay mucho entendimiento de exactamente cómo escoger ciertos parámetros para los algoritmos que están propuestos.

Y en el caso de Rainbow, se notó que quizás todavía se necesita más investigación acerca de cómo escoger, por ejemplo, el parámetro de cuántas variables y cuántas ecuaciones.

Así es que la competición va a seguir encontrando ataques.

Sí, efectivamente, toda la retroalimentación y los nuevos estudios que haya sobre estos nuevos, sobre estos candidatos, creo que es importante y no debería sorprendernos que algún día de estos, bueno, alguno de ellos caiga por ya sea un nuevo ataque o alguna vulnerabilidad o algo.

Esto es investigación de última línea y tenemos que estar preparados ante esto y es bueno tener opciones.

Bien, aquí voy a presentar un poquito, vamos a presentar un poquito, manos a la obra usando Go.

Bueno, Go es un lenguaje de programación, fue creado aproximadamente hace 10 años, se utiliza bastante para crear aplicaciones y servidores web, y bueno, es bastante fácil de aprender y fácil de usar, y en Cloudflare lo usamos bastante para nuestros sistemas.

La pregunta aquí es, bueno, ¿cómo utilizo Go para hacer experimentos utilizando criptografía poscuántica?

Bueno, atención aquí, estos algoritmos que mencionamos, a pesar de ser poscuánticos, son algoritmos que pueden correr en cualquier computador, o sea, lo que es difícil es el problema de resolver estos algoritmos o de quebrar estos algoritmos, que necesita una computadora cuántica, pero no quiere decir que uno necesita una computadora cuántica para correr algoritmos poscuánticos.

Sí, sí existen algoritmos que son cuánticos en sí mismos, pero no han sido investigados, muy investigados, no hay una idea realmente de si funcionan, pero existen.

Sí, y bueno, entonces, yendo detrás de esta investigación de algoritmos poscuánticos, bueno, necesitamos utilizar Go, utilizar implementaciones que sean lo suficientemente rápidas, a veces necesitamos utilizar ensamblador cuando es necesario, y bueno, necesitamos tener esta habilidad, poder hacerlo de forma ágil, y también, ¿por qué no?, retribuir a la comunidad con código abierto, código que está disponible para todo el mundo.

Es por eso que, una de las razones por que creamos esta biblioteca criptográfica, que se llama Circle, y que contiene una cantidad de algoritmos, tanto poscuánticos como algoritmos clásicos, dentro de los cuales está, por ejemplo, Cyc, CyDH, CyCy, tenemos Dilithium y Kyber.

Entonces, vamos a hacer un pequeño demo de esta librería, y van a ver cómo es simple, utilizando Go, utilizando código que ya está listo para todo el mundo usar, y poder instanciar estos algoritmos.

Bien, aquí del lado izquierdo tenemos una pequeña función en Go, que lo que hace es la generación de llaves, utilizando el esquema Cyc.

En este caso, por ejemplo, tenemos a Bob, que él quiere generar un par de llaves.

La llave, lo que es su llave pública, digamos esta llave con nubecita, y su llave privada, que es esta llave más antigua.

Lo único que tiene que hacer Bob, de su lado, es importar el paquete Circle, el módulo Circle, en este entorno, y generar tanto su llave privada como su llave pública.

Y esto crea los objetos por sí mismos, y llamará a la generación utilizando una fuente de números aleatorios.

Y finalmente, Bob tendrá su par de llaves correspondientes.

Una vez que Bob ya tiene sus llaves, ¿qué es lo que puede hacer con ellas?

Bueno, digamos Alice, o una otra persona, lo que quiere hacer es encapsular una llave.

¿Qué quiere decir esto? A final de cuentas, Alice quiere que esta llave sea compartida tanto por Bob y por ella.

Entonces lo que hace es, bueno, toma esta llave, la cifra, con la llave pública de Bob, y se la manda.

Una vez que Bob recibe esto, tiene la habilidad de desencapsular esta llave, es decir, abrir este sobrecito que viene cifrado, y utilizar su llave privada para obtener esta llave.

Finalmente, bueno, después de ejecutar este protocolo, ambos tendrán la misma llave, al final, compartida.

Y esto, bueno, es utilizando Psyche, que es un criptoestado postcuantico.

Ahora tenemos la generación, por ejemplo, de firmas.

¿Quieres? Funciona casi de la misma forma como Armando dijo, porque para la generación de firma igual necesitamos generar, en este caso Alice necesita generar una llave pública y una llave privada.

Genera dichas firmas, y utilizándola, su llave privada, toma un texto, que en este caso es hasta la lista Baby, y lo firma, y genera la firma, y manda su firma.

Entonces, cuando Bob lo va a recibir, hay una función que se llama Verifica, y lo que hace Bob es que toma la llave pública de Alice, porque Alice la publicó en algún lado, o la mandó también como parte de su transmisión, y verifica la firma, y si es que retorna un booleano usualmente que dice, sí, está muy bien, verdadero, la firma es verificada, y si no, retorna falso, y es falsa.

Sí, como ven la interfaz es muy simple, entonces pueden utilizar, en este caso estamos utilizando el Deletion para calcular lo que es una firma digital.

Y bien, los invitamos tanto a usar como a contribuir en este proyecto, el código es código libre, tiene implementaciones que están optimizadas para ABI, AVX2, o para arquitectura ARM64.

Aparte de los algoritmos poscuánticos, hay algoritmos clásicos sobre quantum, que es lo clásico, la aritmética de curvas elípticas, aritmética de cuerpos y de grupos primos, y también algunos otros protocolos más avanzados, que es la interpretación híbrida, o el cálculo de OPRFs, métodos de encapsulación, y también ejecución en paralelo.

Hasta ahora, ¿cuál es tu experiencia en Go, Sophie?

Al utilizar el lenguaje de programación es muy eficiente el momento de programar, en el sentido de que una de las cuestiones que Go, en su inicio, cuando decidieron escribir el lenguaje de programación, lo que quisieron primero enfocarse es que sea un lenguaje simple, por lo tanto su sintaxis es demasiado simple, es un lenguaje seguro en el sentido de que utiliza un recolectador de basura que implementa un compilador con un algoritmo de tres colores, entonces manda la memoria que necesita bastante eficientemente, entonces para escribir criptografía es un lenguaje de programación muy eficiente.

Y algo que realmente ha sido muy bueno es que cuando nosotros lo hemos utilizado con la suite que está escrita en Go, que es la suite de TLS, ha sido muy fácil incorporar experimentos a esa suite.

Así es, bueno, entonces ya tenemos esta librería lista, ahora necesitamos pasar a la experimentación.

Bueno, ahora vamos a ver lo que es los experimentos de TLS. Entonces obviamente hablamos ya bastante acerca de las máquinas cuánticas y lo que significan, y obviamente si es que una máquina cuántica comienza a aparecer, el primer punto donde todo va a colapsar es TLS, porque TLS es este protocolo de comunicación segura que utilizamos básicamente cuando visitamos casi toda página web.

Espero que en el futuro sea toda página web, pero ahora es casi toda página web.

Para hacer transacciones seguras, para visitar, para hacer login, para todo usualmente se utiliza TLS.

Entonces si es que existen máquinas cuánticas en un momento, TLS va a ser roto porque usa algoritmos que son de curvas elípticas o RCA.

¿Cuál ha sido la idea? Han habido varias ideas de bastantes personas de incorporar algoritmos poscuánticos a la suite de TLS, y han habido propuestas de, por ejemplo, hacer un TLS híbrido en donde en la misma handshake de TLS se incluyan algoritmos poscuánticos a la par de algoritmos clásicos.

¿Cuál es el problema con esto? Es que usualmente solo genera cierta protección transitoria, pero no realmente una protección completa en un mundo donde hay computadoras cuánticas.

Entonces la idea con un experimento que ahora estamos corriendo en el Cloudflare es no solamente dar esta protección transitoria, sino realmente dar una protección completa si es que las computadoras cuánticas van a aparecer.

Dale, siguiente. El experimento es QEM-TLS.

¿Qué es QEM? QEM es este mecanismo que viene de las siglas en inglés que significa Key Encapsulation Mechanism.

Es similar a lo que intenta hacer Vicky Gelman en el sentido de que utiliza valores públicos para generar un secreto compartido.

¿Cuál es la idea en el experimento? La idea en el experimento es que tanto el secreto compartido que se genera en TLS sea protegido en un mundo donde hay computadoras cuánticas, como también la parte de la autentificación.

Entonces tanto una seguridad frente a computadoras cuánticas en la autentificación y en la confidencialidad.

¿Qué es lo que hacemos? Es que en vez de utilizar firmas digitales poscuánticas, utilizamos QEMs.

¿Por qué utilizamos QEMs?

Porque son, porque generan valores mucho más pequeños que utilizar firmas digitales.

Como vimos en una de las tablas que mostró Armando, los valores más grandes generados por los algoritmos poscuánticos son en firmas.

Entonces no queríamos utilizar firmas, sino utilizar QEMs que dan valores mucho más pequeños.

El experimento de Clawflare es integrar estos QEMs y esta seguridad poscuántica, tanto en autentificación como en confidencialidad, a la suite de TLS en su versión 1.3 y ver cómo funciona en el mundo real.

Es decir, quizás tomar ciertas conexiones y ver qué es lo que sucede si se incorporan algoritmos poscuánticos durante estas conexiones.

Básicamente ahorita estamos haciendo el experimento en Golan y estamos utilizando la suite de TLS de Golan.

Nuestro propio fork del lenguaje de Golan, porque no podíamos cambiar directamente el lenguaje de Golan porque es un experimento y cambiar un lenguaje en producción con un experimento no es muy razonable.

Pero decidimos hacer nuestro propio fork para poner los experimentos. Y básicamente, como ya les dije, el experimento de seguridad poscuántica todavía usa certificados, porque de cierta forma todavía hay que publicar cuál es la firma poscuántica que se está utilizando.

Obviamente como un experimento no podemos cambiar todas las autoridades de certificación para que utilicen algoritmos poscuánticos, porque tomaría mucho tiempo y convencimiento y no creo que realmente pase.

Pero lo que podemos utilizar es una extensión de TLS que se llama credenciales delegados.

Los detalles de las implementaciones se encuentran en estas dos pull requests que pueden ver.

Una de esas no está completa, pero de todas maneras pueden ver cómo el experimento se va desarrollando.

Y con eso creo que tenemos los últimos pensamientos finales.

Sí, bueno, de mi parte agradecerles a todos por su atención.

Espero que este tema les interese bastante. Tenemos ahora lo que es la investigación de estos parámetros, de este algoritmo poscuántico usando QEM.

Y bueno, como siempre, esperamos les haya gustado.

Igual que esperamos que les haya gustado. Todavía hay bastantes cosas que necesitan ser pensadas en cuanto a la criptografía poscuántica.

Todavía hay bastantes cosas que pensar, pero vamos en un buen camino y todos estos experimentos son hechos precisamente para lograr incorporar algoritmos poscuánticos a las suites y los protocolos criptográficos que ahorita nosotros tenemos.

Porque como les dijimos, como parte de la comunidad criptográfica es mejor ser prevenidos antes de que vengan las computadoras cuánticas y destruyan toda la Internet.

Bueno, ojalá eso pase en algún tiempo porque aún estoy cifrando con curvas elípticas.

Entonces es un poco scary esto. Bueno, agradecemos su atención y bueno, los esperamos y ojalá utilicen, lean los blog posts que están marcados ahí.

Y muchas gracias. Muchas gracias, Juan. Gracias.