POKEx: Performance analysis of POKE-key exchange and SIDH-variants

Imagina que el internet es una ciudad gigante y bulliciosa donde todos se envían cartas secretas unos a otros. Para mantener estas cartas seguras de los ladrones, usamos "cerraduras" llamadas cifrado. Durante décadas, las mejores cerraduras se hicieron utilizando problemas matemáticos que son fáciles de resolver en un sentido, pero increíblemente difíciles de deshacer, como mezclar colores de pintura. Sin embargo, los científicos están preocupados porque, en el futuro, las computadoras superpotentes (llamadas computadoras cuánticas) podrán deshacer estas cerraduras instantáneamente, dejando nuestros secretos totalmente expuestos. Para evitar esto, los investigadores están construyendo nuevas cerraduras basadas en una rama extraña y hermosa de las matemáticas llamada "isogenia". Piensa en las isogenias como un tipo especial de puente que conecta diferentes formas (curvas matemáticas). El secreto de la cerradura es el camino específico que tomas a través del puente. Durante mucho tiempo, el diseño de puente más popular se llamó SIDH. Era famoso porque las cerraduras eran diminutas y rápidas, lo que lo convirtió en un fuerte contendiente para proteger nuestro futuro mundo digital.

Pero entonces, en 2023, un par de investigadores descubrieron un truco ingenioso para romper el puente SIDH. Encontraron que los diseñadores del puente habían dejado accidentalmente un mapa del camino visible para cualquiera que mirara, permitiendo así deducir la ruta secreta en segundos. Esto fue un gran golpe, ya que significaba que la cerradura más prometedora para ser "resistente al quantum" estaba, en realidad, rota. Desde entonces, los científicos han estado intentando frenéticamente construir nuevos puentes que oculten mejor el mapa. Algunos intentaron cubrir el mapa con una manta (enmascaramiento), mientras que otros intentaron construir el puente con diferentes materiales. La gran pregunta seguía siendo: ¿Podemos construir un puente que sea tanto inquebrantable como lo suficientemente rápido para usarse en el mundo real?

Este artículo, titulado "POKEx", entra en ese sitio de construcción caótico para probar un nuevo y brillante diseño de puente llamado POKÉ. Los autores, Hyeonhak Kim y Suhri Kim, decidieron convertir el método de cifrado POKÉ en un sistema completo de intercambio de claves (al que llaman POKEx) y ponerlo a competir contra los otros principales contendientes que intentan arreglar el puente SIDH roto. No solo adivinaron; construyeron versiones funcionales de estos sistemas y los cronometraron en una computadora potente. Su principal hallazgo es que POKEx es actualmente el más rápido y eficiente de todos los puentes basados en isogenias. En sus pruebas, fue aproximadamente 21 veces más rápido que la siguiente mejor alternativa (terSIDH) y casi 65 veces más rápido que otro diseño popular (CSIDH). Aunque todavía es más lento que otros tipos de cerraduras resistentes al quantum, su velocidad y tamaño diminuto lo convierten en un candidato muy prometedor para el futuro, ofreciendo una forma de mantener nuestros secretos digitales seguros sin ralentizar el internet.

La historia del puente roto y la nueva solución

Para entender por qué este artículo es importante, primero debemos mirar el problema del "puente". En el mundo de la criptografía, un "intercambio de claves" es como dos personas poniéndose de acuerdo en una contraseña secreta sin decirla nunca en voz alta. Durante mucho tiempo, el sistema SIDH fue la estrella. Utilizaba curvas elípticas supersingulares —piensa en estas como formas complejas y onduladas en un universo matemático—. La magia de SIDH era que utilizaba "puntos de torsión", que son como puntos de referencia específicos en estas curvas, para construir el puente. El sistema era tan eficiente que tenía claves pequeñas (el equivalente digital de una cerradura diminuta y ligera) y era muy rápido.

Sin embargo, el puente SIDH tenía un fallo fatal. Para construir el puente, el sistema tenía que publicar cierta información sobre los puntos de referencia (puntos de torsión) que utilizaba. En 2023, Castりck y Decru encontraron una forma de usar estos puntos de referencia publicados, combinados con un truco matemático ingenioso llamado "Kani's glue-and-split", para reconstruir el camino secreto. Era como dejar un rastro de migas de pan que conducía directamente al tesoro. Una vez que este ataque fue descubierto, SIDH fue considerado roto y eliminado de la lista de candidatos para el futuro de la seguridad en internet.

La carrera para arreglar el puente

Después de la caída de SIDH, la comunidad criptográfica no se rindió. Comenzaron a construir nuevos puentes para reemplazarlo. Algunos intentaron ocultar los puntos de referencia cubriéndolos con ruido aleatorio (un método llamado M-SIDH). Otros intentaron cambiar la forma del puente por completo usando "orientación artificial" (terSIDH). También existía CSIDH, un tipo diferente de puente que no se vio afectado por el mismo ataque, pero que tenía sus propios problemas de velocidad.

El problema era que estos nuevos puentes eran demasiado lentos o demasiado grandes. Cubrir los puntos de referencia con ruido requería números mucho más grandes para mantenerse seguro, lo que hacía que las cerraduras fueran pesadas y lentas de usar. Cambiar la forma del puente (terSIDH) ayudó, pero todavía presentaba variaciones de velocidad que podrían ser peligrosas. La comunidad necesitaba una solución que fuera tanto segura como rápida.

Entra POKEx: El demonio de la velocidad

Aquí es donde el nuevo héroe del artículo, POKEx, entra en escena. POKEx se basa en un esquema llamado POKÉ, que fue propuesto recientemente por Basso y Maino. Los autores de este artículo tomaron POKÉ y lo convirtieron en un sistema completo de intercambio de claves, con todos los pasos necesarios para generar claves e intercambiar secretos de forma segura.

El ingrediente secreto de POKEx es cómo maneja los "puntos de referencia". En lugar de usar solo caminos unidimensionales como el antiguo SIDH, POKEx utiliza una "representación bidimensional". Imagina intentar cruzar un río. SIDH era como caminar sobre un solo tablón. Si alguien veía dónde pisabas, podía deducir tu camino. POKEx, sin embargo, es como caminar sobre una cuadrícula de tablones donde puedes moverte en dos direcciones a la vez. Esto hace que el camino sea mucho más difícil de adivinar. Además, POKEx utiliza un tipo especial de campo matemático (un número primo de la forma $2^a3^b5^c-1$) que permite cálculos muy rápidos, a diferencia de los otros nuevos puentes que tenían que usar números mucho más grandes y lentos.

El gran enfrentamiento: Lo que dicen los números

Los autores no solo hablaron de POKEx; lo pusieron a prueba. Construyeron software para ejecutar POKEx junto con los otros principales contendientes: M-SIDH, terSIDH y CSIDH. Los configuraron todos al mismo nivel de seguridad (nivel de seguridad NIST 1, que es el estándar para proteger datos gubernamentales de alto secreto) y cronometraron cuánto tiempo tomaba realizar un intercambio de clave.

Los resultados fueron sorprendentes.

• M-SIDH fue el más lento del grupo, tardando casi 190 segundos en hacer lo que POKEx hizo en una fracción de segundo. Los autores señalaron que esto hace que M-SIDH sea poco práctico para el uso en el mundo real.
• terSIDH fue mucho más rápido que M-SIDH, pero aun así tardó unos 6.5 segundos.
• CSIDH tardó unos 20 segundos.
• POKEx, sin embargo, terminó el trabajo en solo 306.95 milisegundos (aproximadamente 0.3 segundos).

Para poner esto en perspectiva, POKEx fue 21.21 veces más rápido que terSIDH y 64.97 veces más rápido que CSIDH. Esto convierte a POKEx en el actual campeón del intercambio de claves basado en isogenias.

¿Es perfecto?

El artículo tiene cuidado de no llamar a esto una solución "perfecta". Aunque POKEx es el más rápido entre los puentes de isogenia, sigue siendo mucho más lento que otros tipos de cerraduras resistentes al quantum, como ML-KEM (que tomó solo 0.10 milisegundos en la prueba). Sin embargo, los autores señalan un compromiso crucial. ML-KEM es rápido, pero sus "cerraduras" (claves públicas y textos cifrados) son enormes, ocupando mucho espacio en internet. POKEx, por otro lado, tiene claves muy pequeñas (solo 324 bytes para la clave pública), lo que significa que utiliza menos ancho de banda. En un mundo donde la velocidad de internet y los límites de datos importan, este tamaño pequeño es una ventaja masiva.

La conclusión

Este artículo demuestra que, si bien el viejo puente SIDH está roto, el camino hacia un nuevo puente seguro está abierto. POKEx es actualmente el candidato más prometedor en la familia de las isogenias, ofreciendo una combinación poco común de alta velocidad y tamaño reducido. Demuestra que podemos construir cerraduras resistentes al quantum que no ralenticen nuestras vidas digitales. Aunque todavía necesita más trabajo para alcanzar la velocidad de otros métodos resistentes al quantum, su eficiencia sugiere que podría convertirse en una herramienta vital para mantener seguro nuestro futuro internet, especialmente en situaciones donde ahorrar espacio de datos es tan importante como ahorrar tiempo.