FrodoKEM: Un Key-Encapsulation Mechanism Quantum-Safe (PQC) que recibe su nombre por «El señor de los Anillos»

No hace mucho os hablaba de HQC «Hamming Quasi-Cyclic» el segundo KEM (Key-Encapsulation Mechanism) elegido por el NIST para completar al primero que se anuncio y que fue bautizado como  Module-Latice-Based KEM, o MLB-KEM o ML-KEM. Estos dos primeros KEM han sido elegidos como parte de la estandarización de los algoritmos de Criptografía Post-Cuántica (PQC: Post-Quantum Cryptography). 

Sin embargo, hubo otros que se quedaron en el camino, y que con la aceleración de los últimos anuncios de Google Willow Quantum Chip, Microsoft Majorana-1 y Amazon Ocelot Quantum Chip,  merece la pena conocerlos porque alguno se está convirtiendo en estándar ISO. Uno de ellos es FrodoKEM, en el que han colaborado el mundo de la universidad, investigadores de Google y de Microsoft, que incluso tienes publicado en su GitHub para que lo puedas probar.

Si queréis conocer más información de  Module-Latice-Based KEM, o MLB-KEM o ML-KEM, la podéis encontrar en la publicación completa del standard de ML-KEM la tenéis documentada en el siguiente paper del NIST, y yo escribí un artículo de HQC «Hamming Quasi-Cyclic», que también podéis leer.

Estos dos algoritmos se basan en una estructura de anillo algebraica central para esos algoritmos, y la apuesta de Frodo «es librarse del anillo». Sí, has entendido correctamente, este algoritmo recibe su nombre en homenaje al mítico personaje «Frodo» de «El señor de los anillos«, que si no te has leído el libro, estás tardando ya – yo le dediqué un verano y lo disfruté como un «enano».

En este caso, FrodoKEM utiliza, para la generación de las claves de cifrado PQC (Post-Quantum Cryptography) que se usarán en una solución PKI se basan en la dificultad de resolver el problema de Learning With Errors. En este caso, el problema radica en dada una matriz A cuadrada de n x n generada uniformemente aleatoria, y dos matrices lineales siendo una muestra s de la clave, pero teniendo además la matriz e «errores«, se realiza el cálculo de A x s + e y se obtiene una matriz b.

Para un atacante la dificultad del algoritmo es resolver la inversa, es decir, dado A y el resultado b, encontrar s, que sería la derivada sampleada de la clave, que no sería fácil de resolver para un algoritmo cuántico por la explosión de probabilidades en los que se ha podido inyectar el error, lo que le obliga a descubrir la matriz de errores, además de la clave. Como se puede ver en la imagen siguiente, la clave pública está compuesta de sA y b, por lo que se hace complejo resolver el problema.

Esta es la base fundamental de FrodoKEM, que como bien explican en la web de «FrodoKEM» y en el artículo «FrodoKEM: A conservative quantum-safe cryptographic algorithm» fue descartado del proceso de estandarización de NIST en la Ronda 3, pero va a ser estandarizado por la ISO/IEC 18033-2 para que sea un estándar que pueda ser utilizado por cualquiera que lo desee en la industria. 

El problema que tiene FrodoKEM, como bien explican, es que evitar las posibles vulnerabilidades criptográficas que puede tener en el futuro el «anillo algebraico» en el que se centran ML-KEM y HQC-KEM es un coste en tamaño y en ciclos de computación.

Así que, si no tenías lectura para estos días, ya sabes qué te puedes comenzar a leer, que esto es fundamental para entender el mundo de la seguridad informática en cualquiera de las áreas profesionales en la que te quieras especializar.

¡Saludos Malignos!