La criptografía basada en retículos (o lattice-based cryptography) es, en términos sencillos, el futuro de la seguridad digital. Es una de las ramas más prometedoras de la criptografía post-cuántica, diseñada para resistir ataques incluso de ordenadores cuánticos superpotentes. Veremos paso a paso el algoritmo CRYSTALS-Kyper conocido ahora como FIPS 203.

A. Los Retículos

1. ¿Qué es un «retículo»?

Imagina una cuadrícula infinita de puntos en un espacio de varias dimensiones. En matemáticas, un retículo es un conjunto de puntos en el espacio n-dimensional con una estructura periódica.

Se construye a partir de un conjunto de vectores llamados base. Combinando estos vectores (sumándolos o restándolos), puedes llegar a cualquier punto de la rejilla, malla o red.

2. El problema matemático: ¿Por qué es seguro?

La seguridad de esta criptografía no se basa en factorizar números primos (como el RSA), sino en problemas geométricos que son increíblemente difíciles de resolver para una computadora si el número de dimensiones es alto (por ejemplo, 500 o más dimensiones).

Los dos problemas principales son:

• SVP (Shortest Vector Problem): Dado un retículo, el objetivo es encontrar el punto más cercano al origen (el vector más corto).
• CVP (Closest Vector Problem): Dado un punto cualquiera en el espacio, el objetivo es encontrar el punto del retículo que esté más cerca de él.

Parece fácil en un dibujo de 2D, pero en 500 dimensiones, encontrar ese punto es como buscar una aguja en un pajar del tamaño de una galaxia.

3. ¿Por qué es «Post-Cuántica»?

La mayoría de la criptografía que usamos hoy (RSA, Curva Elíptica) se basa en problemas matemáticos que un ordenador cuántico puede resolver en minutos usando el Algoritmo de Shor.

Sin embargo, hasta donde sabemos, los ordenadores cuánticos no tienen una ventaja significativa para resolver los problemas de retículos. Son tan difíciles para una PC de escritorio como para una máquina cuántica. Por eso, organismos como el NIST (EE. UU.) ya han seleccionado algoritmos basados en retículos como CRYSTALS-Kyber, para que sean los nuevos estándares de seguridad global.

Ventajas principales

• Eficiencia: A diferencia de otros métodos post-cuánticos, los esquemas de retículos son rápidos y no requieren claves de un tamaño monstruoso.
• Versatilidad: Permiten crear cosas increíbles como el Cifrado Totalmente Homomórfico (FHE), que permite procesar datos sin necesidad de descifrarlos, puedes sumar números cifrados y que el resultado siga cifrado y al descifrarlos que dé el resultado de la suma sin cifrar.
• Seguridad demostrable: Se puede demostrar matemáticamente que romper el código es tan difícil como resolver los problemas de retículos más complejos.

En resumen: Si el RSA es un candado basado en la dificultad de deshacer una multiplicación, la criptografía de retículos es un laberinto multidimensional donde es imposible orientarse sin la llave correcta.

B. El Problema del Vector más pequeño

El SVP (Shortest Vector Problem) es el corazón de la seguridad en retículos. Para entenderlo, imagina que te doy las instrucciones para moverte por una ciudad, pero solo puedes dar pasos de longitudes muy específicas. ¿Cómo llegarías al destino?

Aquí tienes un ejemplo práctico de cómo se plantea y cómo se resuelve en una dimensión baja (donde aún es fácil de entender).

1. El Problema: El «Camuflaje» de la Base

Un retículo puede representarse con diferentes bases (conjuntos de vectores). El truco de la criptografía es darte una mala base, vectores largos y casi paralelos para que no se encuentre fácilmente el camino más corto.

Ejemplo en 2D:

Supongamos que te doy los siguientes dos vectores como base de un retículo:

• u = (10, 2)
• v = (9, 2)

A simple vista, ambos son vectores largos. El objetivo del SVP es encontrar el vector más corto posible, que no sea el punto cero, combinando estos dos vectores mediante sumas o restas enteras. Es decir, la combinación lineal de esos vectores más cerca del origen de coordenadas.

2. ¿Cómo se resuelve? (Algoritmo de Gauss)

En 2 dimensiones, el problema se resuelve con un algoritmo similar al de Euclides para encontrar el máximo común divisor, llamado Reducción de Gauss.

Nota: Algoritmo de Euclides: es un método eficiente para encontrar el máximo común divisor (MCD) de dos números enteros, basado en dividir el mayor entre el menor y sustituir el mayor por el resto sucesivamente hasta obtener un residuo cero. El MCD es el último divisor no nulo de este proceso de divisiones.

Nota: El algoritmo de reducción de Gauss es un método para transformar un sistema de ecuaciones lineales en una forma escalonada superior (triangular) mediante operaciones elementales de fila. El objetivo es simplificar la matriz aumentada del sistema para resolverla fácilmente mediante sustitución hacia atrás, convirtiendo los elementos debajo de la diagonal principal en ceros.

El objetivo es acortar los vectores restando múltiplos de uno al otro hasta que ya no se puedan hacer más pequeños.

Paso a paso del ejemplo:

1. Comparar: Tenemos u = (10, 2) y v = (9, 2).
2. Reducir: Restamos u – v = (10-9, 2-2) = (1, 0).
3. Actualizar la base: Ahora nuestra base es v = (9, 2) y u’ = (1, 0).
4. Intentar reducir más: ¿Podemos usar u’ para hacer más pequeño a v? Sí, restando 9 veces el vector u’:(9, 2) – 9(1, 0) = (0, 2)
5. Resultado: Nuestra base final es la nueva base {u’, v’} = {(1, 0), (0, 2)}.

El vector más corto (SVP) es (1, 0). Su longitud es 1, mucho menor que los vectores originales de longitud aproximada: 10.19 y 9.21.

3. ¿Por qué esto es seguro en criptografía?

El ejemplo anterior fue en 2 dimensiones. En ese nivel, una computadora lo resuelve en microsegundos.

Sin embargo, en la criptografía real:

• Usamos 500 o 1000 dimensiones.
• En dimensiones tan altas, no existe un «Algoritmo de Gauss» eficiente.
• Los algoritmos disponibles (como el LLL o BKZ) solo encuentran vectores relativamente cortos, pero no el más corto.
• Encontrar el vector exacto en 500 dimensiones tomaría miles de años incluso para las supercomputadoras actuales.

Dato curioso: El algoritmo LLL (Lenstra-Lenstra-Lovász), que es una versión avanzada de lo que acabamos de hacer, es tan importante que se usa no solo en criptografía, sino también para romper otros sistemas antiguos y en teoría de números pura.

C. Criptosistemas De Retículos

La criptografía basada en retículos ha pasado de ser una curiosidad académica a convertirse en el estándar mundial de seguridad. El NIST (Instituto Nacional de Estándares y Tecnología de EE. UU.) ya ha seleccionado a los ganadores que protegerán nuestras comunicaciones en la era cuántica. Aquí tienes los algoritmos más importantes clasificados por su función.

1. Los «Estándares de Oro» (Seleccionados por el NIST)

Estos son los algoritmos que verás implementados en navegadores, VPNs y bancos en los próximos años.

• CRYSTALS-Kyber (ahora llamado ML-KEM):
  • Función: Cifrado y establecimiento de claves (KEM).
  • Uso: Es el algoritmo principal para asegurar que, cuando te conectas a una web (HTTPS), la llave que cifra la sesión sea segura contra ataques cuánticos.
  • Por qué destaca: Es extremadamente rápido y sus claves tienen un tamaño muy equilibrado (ni muy grandes ni muy pequeñas).
• CRYSTALS-Dilithium (ahora llamado ML-DSA):
  • Función: Firmas digitales.
  • Uso: Sirve para verificar que un documento, un software o un mensaje realmente viene de quien dice venir y no ha sido alterado.
  • Por qué destaca: Es muy robusto y fácil de implementar de forma segura en hardware.

2. Los Especialistas y Veteranos

• Falcon:
  • Función: Firmas digitales.
  • Uso: Situaciones donde el ancho de banda es crítico (como en chips muy pequeños o tarjetas inteligentes).
  • Dato curioso: Produce las firmas más pequeñas entre los algoritmos de retículos, pero es matemáticamente mucho más complejo de programar que Dilithium.
• NTRU (Number Theorists Are Us):
  • Función: Cifrado.
  • Historia: Es el «abuelo» de los retículos. Fue inventado en los años 90 y, aunque no fue el ganador principal del NIST, es extremadamente confiable porque lleva décadas resistiendo ataques sin ser vulnerado.

3. Cifrado Homomórfico (El «Santo Grial»)

Estos algoritmos son la «magia negra» de los retículos. Permiten hacer cálculos con datos sin necesidad de descifrarlos.

• TFHE / BGV / CKKS:
  • Uso: Computación en la nube privada. Por ejemplo, podrías enviar tus datos médicos cifrados a una IA en la nube; la IA analiza los datos (estando cifrados), genera un diagnóstico y te lo devuelve. Nadie, ni siquiera el dueño de la nube, ve tus datos reales.
  • Base: Todos ellos funcionan gracias a un problema de retículos llamado LWE (Learning With Errors).

Comparativa rápida

Algoritmo	Tipo	Fortaleza
Kyber	Cifrado	El estándar más equilibrado y rápido.
Dilithium	Firma	Muy seguro y fácil de usar en aplicaciones generales.
Falcon	Firma	Firmas muy compactas (ahorra espacio).
NTRU	Cifrado	Veterano, muy estudiado y libre de patentes.
CKKS	Homomórfico	Permite procesar datos científicos mientras están cifrados.

---

Nota: Sabías que Google Chrome y Cloudflare ya han empezado a implementar versiones de Kyber en su tráfico real. Es muy probable que ya estés usando criptografía de retículos en este momento sin saberlo.

D. CRYSTALS-KYPER, ML-KEM, FIPS 203

ML-KEM, anteriormente conocido como CRYSTALS-Kyber, no es un algoritmo de cifrado tradicional de mensaje largo, sino un KEM (Key Encapsulation Mechanism). Su trabajo es asegurar que dos personas puedan acordar una clave secreta (de 256 bits) a través de un canal inseguro, la cual luego se usa con otro algoritmos simétrico como AES para cifrar los datos reales.

Se basa en el problema de M-LWE (Module Learning With Errors). Aquí tienes los pasos técnicos detallados de cómo funciona este algoritmo matemático.

Conceptos Previos: Los Bloques de Construcción

Antes de empezar, debes saber que todo sucede dentro de un anillo de polinomios. En lugar de números simples, ML-KEM opera con polinomios donde los coeficientes son números pequeños (módulo 3329), es decir, en el cuerpo de Z sub 3329, 3329 es un número primo.

Definimos:

• A: Una matriz pública de polinomios (generada al azar).
• s: El vector secreto (polinomios con coeficientes muy pequeños).
• e: El error o ruido (polinomios para camuflar el secreto, con coeficientes entre -2 y 2).

Paso 1: Generación de Claves

El receptor, llamémosle Alicia, prepara su buzón.

1. Generar la matriz A: Se usa una semilla aleatoria para generar una matriz pública A de tamaño k x k.
2. Elegir el secreto: Alicia elige un vector secreto s y un vector de error e, ambos con coeficientes muy pequeños.
3. Calcular la clave pública: Realiza la operación:t = A s + e mod q
4. Resultado:
   • Clave Pública: (t, A).
   • Clave Privada: s.

Paso 2: Encapsulación (Cifrado de la clave)

El emisor (Bob) quiere enviarle a Alicia una clave secreta para hablar por privado. Clave que posteriormente usarán con un cifrado simétrico.

1. Generar el mensaje m: Bob crea una cadena de 256 bits aleatorios, la clave que quiere compartir.
2. Añadir ruido de Bob: Bob elige su propio vector de ruido r y dos errores e_1 (vector) y e_2 (escalar), todos muy pequeños.
3. Calcular el criptograma c = (u, v):
   • u = A^T r + e_1 (Esto envuelve el movimiento de Bob con la matriz pública).
   • v = t^T r + e_2 + mAquí, el mensaje m se esconde sumándolo al resultado de la clave pública de Alicia multiplicada por el ruido de Bob.
4. Enviar: Bob envía el par (u, v) a Alicia.

Paso 3: Desencapsulación (Recuperación de la clave)

Alicia recibe u, v) y usa su llave secreta s para extraer el mensaje m.

1. La resta mágica: Alicia calcula un valor aproximado:m’ aproximado v – s^T u¿Por qué funciona? Si sustituimos las fórmulas anteriores:v – s^T u = (t^T r + e_2 + m) – s^T (A^T r + e_1)Como t es aproximadamente A s, entonces t^T r es (A s)^T r = s^T A^T r.Los términos grandes se cancelan y queda:Resultado = m + pequeños errores
2. Limpieza: Alicia aplica una función de decodificación que elimina el pequeño ruido restante, recuperando el mensaje m exacto, los 256 bits originales de la clave.

¿Qué lo hace tan especial?

Lo que acabas de ver es el esquema PKE (Cifrado de Clave Pública). Sin embargo, ML-KEM añade una capa extra llamada Transformación Fujisaki-Okamoto (FO).

• Si alguien intenta enviar un mensaje malformado para engañar a Alicia y descubrir su clave privada, la transformación FO detecta la anomalía y genera una clave falsa aleatoria en lugar de un error.
• Esto hace que ML-KEM sea IND-CCA2 (seguro contra ataques de texto cifrado escogido), el estándar más alto de seguridad.

Resumen de parámetros

• ML-KEM-512: Seguridad equivalente a AES-128.
• ML-KEM-768: El «punto dulce» equivalente a AES-192.
• ML-KEM-1024: Seguridad máxima equivalente a AES-256.

E. Ejemplo

Para entender cómo funciona ML-KEM (CRYSTALS-Kyber) en la práctica, tenemos que hacer una pequeña trampa didáctica. El algoritmo real usa polinomios de 256 grados y matrices gigantes, lo cual es imposible de calcular a mano.

Para que los pasos sean claros, vamos a usar un «modelo de juguete» (Toy Model) basado en el mismo principio matemático (Learning With Errors), pero usando números enteros simples en lugar de polinomios. Las mecánicas de sumar ruido, multiplicar y redondear son exactamente las mismas que usa Kyber.

Preparación: Las reglas del juego

En este universo matemático, todo funciona dentro de un reloj circular o módulo, es decir, con números en un cuerpo Z sub p, con p primo.

• Nuestro reloj, en este ejemplo, será de 23 posiciones (Módulo 23). Todos los resultados se calculan dividiendo entre 23 y quedándonos con el resto.
• Codificación del mensaje: Para enviar un bit, Bob no envía un «1» o un «0» directamente. Lo escala a nuestro reloj:
  • Si quiere enviar un 0, usa el valor 0.
  • Si quiere enviar un 1, usa el valor 11 (la mitad de 23).

Paso 1: Alicia genera sus claves

Alicia quiere que Bob le envíe un mensaje seguro. Para ello, Alicia crea su candado (Clave Pública) y su llave (Clave Privada).

1. La base pública (A): Alicia elige un número público aleatorio. Usaremos el 15.
2. El Secreto y el Ruido: Alicia elige un número secreto pequeño (s) y un pequeño error/ruido (e).
   • Secreto: s = 4
   • Error: e = 2
3. Calcular la Clave Pública (t): Alicia mezcla la base pública con su secreto y le suma el ruido.
   t = (A s) + e mod(23)
   t = (15 * 4) + 2 = 62
   Como estamos en módulo 23, dividimos 62 entre 23 y nos quedamos con el resto, 16.

• Clave Privada de Alicia: 4
• Clave Pública: (A=15, t=16)

Paso 2: Bob cifra un mensaje (Encapsulación)

Bob quiere enviarle a Alicia el bit secreto 1 (que codificado equivale a 11). Bob toma la Clave Pública de Alicia y añade su propio camuflaje.

1. Variables temporales de Bob: Bob elige un número secreto temporal (r) y dos errores muy pequeños (e_1 y e_2).
   • r = 1
   • e_1 = 1
   • e_2 = -1
2. Primera parte del candado (u): Bob mezcla la base pública con su secreto y su primer error.
   u = (A r) + e_1 mod(23)
   u = (15 * 1) + 1 = 16
3. Segunda parte del candado (v): Bob toma la clave pública de Alicia (t), la mezcla con su secreto temporal, añade su segundo error y suma su mensaje (el 11).
   v = (t r) + e_2 + mensaje mod(23)
   v = (16 * 1) – 1 + 11 = 26
   El resto de dividir 26 entre 23 es 3.

Bob envía su paquete cifrado a Alicia: (u=16, v=3). Si un atacante intercepta esto, solo ve números que parecen aleatorios debido al ruido acumulado.

Paso 3: Alicia descifra el mensaje (Desencapsulación)

Alicia recibe el paquete (16, 3). Para abrirlo, usa su Clave Privada (s = 4).

1. La resta mágica: Alicia toma la segunda parte del paquete (v) y le resta la primera parte (u) multiplicada por su secreto.
   Resultado = v – (u s) mod(23)
   Resultado = 3 – (16 * 4) = 3 – 64 = -61
2. Ajuste del reloj: En módulo 23, un número negativo se arregla sumándole 23 hasta que sea positivo.
   (-61 + 23 + 23 + 23 = 8).
   • El resultado es 8.
3. El paso crucial: Eliminar el ruido: Alicia mira el resultado (8) y se hace una pregunta sencilla: ¿Este número está más cerca del 0 o del 11?
   • La distancia entre 8 y 11 es de solo 3 pasos.
   • La distancia entre 8 y 0 es de 8 pasos.

   Como está mucho más cerca del 11, Alicia sabe con total seguridad que Bob le envió un 1. ¡El descifrado fue un éxito!

¿Qué pasó con el ruido? Todo ese ruido (e, e_1, e_2) se acumuló y movió el resultado perfecto (11) hasta el 8. Mientras el ruido total no sea lo suficientemente grande como para empujar el número a la mitad equivocada del reloj, el redondeo final siempre recuperará el mensaje original intacto.

Este es el esqueleto matemático exacto de ML-KEM. La única diferencia es que, en el mundo real, en lugar de multiplicar números simples, Kyber multiplica matrices de polinomios, lo que crea un escudo de dimensiones matemáticas que los ordenadores cuánticos no pueden atravesar.

F. ML-KEM, CRYSTALS-Kyber con polinomios

Para dar el salto del modelo de juguete a cómo funciona realmente ML-KEM (CRYSTALS-Kyber), tenemos que hablar de polinomios.

En lugar de multiplicar números simples, el algoritmo multiplica matrices llenas de polinomios gigantescos. Esto es lo que se conoce como Module-LWE (M-LWE).

Aquí tienes un vistazo exacto a la anatomía de esta matriz.

1. El bloque de construcción: El Polinomio de Kyber

En ML-KEM todos los polinomios tienen dos reglas estrictas, los parámetros del algoritmo:

1. Grado máximo 255: Tienen 256 términos en total, es decir son polinomios de grado 255. La regla de oro es que X^256 = -1. Si al multiplicar dos polinomios obtienes un X^256, este da la vuelta y cambia de signo.
2. Módulo q = 3329: Todos los coeficientes (los números que acompañan a las X) deben ser números enteros entre 0 y 3328.

Un ejemplo de este tipo de polinomio se vería algo así si lo escribiéramos completo:

2451X^255 + 13X^254 + 3012X^253 + … + 843X^2 + 12X + 3320

2. La Matriz Pública (A)

Dependiendo del nivel de seguridad (ML-KEM-512, 768 o 1024), la matriz A cambia de tamaño. Tomemos como ejemplo ML-KEM-512, el nivel básico, equivalente a AES-128.

En este nivel, la matriz A es de 2 x 2. Pero recuerda, cada elemento de esta matriz es un polinomio completo de 256 términos.

La matriz A se representa matemáticamente así:

p_11(X), p_12(X)

p_21(X), p_22(X)

con p_ij(X) un polinomio completo de 256 términos.

3. ¿Cómo se usa esta matriz en el cifrado?

Siguiendo el ejemplo anterior donde calculábamos la clave pública de Alicia (t = A s + e), en ML-KEM la operación real es una multiplicación de matrices y vectores de polinomios.

• A es la matriz pública de 2 x 2.
• s es un vector columna de 2 x 1 (que contiene dos polinomios secretos muy pequeños, por ejemplo, con coeficientes que solo son: -1, 0, 1).
• e es otro vector columna de 2 x 1 (el ruido, también polinomios con coeficientes diminutos).

La ecuación de la Clave Pública de Alicia se calculo de la manera detallada arriba.

¿Por qué complicarlo con polinomios?

Si usáramos solo matrices gigantes de números normales como en LWE estándar, las claves públicas pesarían megabytes enteros, lo que haría que tu conexión a internet fuera lentísima a la hora de cargar una web segura.

Al usar anillos de polinomios (Module-LWE), ML-KEM empaqueta mucha información matemática en un espacio muy pequeño. Las claves públicas de ML-KEM-512 pesan apenas 800 bytes, lo cual es ultrarrápido de enviar por la red actual.