Estructura del KEM

Resumen

Kyber es un Key Encapsulation Mechanism (KEM), no un esquema de cifrado asimétrico general. Un KEM permite que dos partes acuerden una clave simétrica compartida sin intercambiarla explícitamente. Para cifrar datos, se usa la clave derivada con un cifrado simétrico (AES, ChaCha).

Componentes

Un KEM tiene tres operaciones:

G = KeyGen()               → (pk, sk)
E = Encaps(pk)             → (ct, K)
D = Decaps(sk, ct)         → K

KeyGen — Generación de Claves

1. Generar semilla aleatoria d (32 bytes)
2. Derivar A ∈ R_q^{k×k} de d usando SHAKE-128 (sampling determinista)
3. Muestrear s ∈ R_q^{k} de la distribución CBD(η)
4. Muestrear e ∈ R_q^{k} de la distribución CBD(η)
5. Calcular pk = A·s + e    (codificado como byte array)
6. Almacenar sk = (s, pk)   (o una forma hash para desencapsulación más rápida)
7. Devolver (pk, sk)

Notable: La matriz A se genera de forma determinista a partir de una semilla. Esto significa que A no necesita almacenarse ni transmitirse — cualquiera que conozca la semilla puede reconstruirla.

Encaps — Encapsulación

Input: pk

1. Generar una moneda aleatoria m (32 bytes)
2. Derivar (K, r) = G(m || H(pk))   usando SHA3-256/SHAKE256
   donde G es un hash, H es otro hash
3. Calcular t = H(m)                  (commitment implícito)
4. Cifrar m usando pk y la aleatoriedad r:
   a. Muestrear s' ∈ R_q^{k} de CBD(η) usando r
   b. Muestrear e1 ∈ R_q^{k} de CBD(η)
   c. Muestrear e2 ∈ R_q de CBD(η)
   d. Calcular u = NTT^{-1}(Â·NTT(s')) + e1
   e. Calcular v = NTT^{-1}(t^T·NTT(s')) + e2 + Decompress_q(m, 1)
5. Devolver ct = (u, v)   y   K

Decaps — Desencapsulación

Input: sk, ct = (u, v)

1. Descifrar:
   a. m' = Compress_q(v - s^T·u, 1)
2. Reprocesar:
   a. (K', r') = G(m' || H(pk))
   b. Re-ejecutar Encaps usando m' y r'
   c. Comparar resultado con ct recibido
3. Si coincide: devolver K'
   Si no coincide: devolver clave pseudoaleatoria derivada de (sk, ct)

El paso de reprocesamiento y comparación (Fujisaki-Okamoto transform) es lo que hace a Kyber CCA-secure. Sin él, el KEM sería vulnerable a ataques de texto cifrado adaptativo.

El Flujo Completo

Alice                          Bob
  |                              |
  |--- (pk = A·s + e) --------->|  (KeyGen de Alice)
  |                              |
  |<--- (ct = (u,v), K) --------|  (Encaps usando pk de Alice)
  |                              |
  |--- descifra ct con s -------|  (Decaps: recupera K)
  |                              |
  |--- (usa K para AES/ChaCha) -|  (comunicación cifrada)

Importante: A diferencia de RSA o ECDH, en Kyber el receptor genera el par de claves y el emisor genera el ciphertext y la clave. Es asimétrico en direcciones: la encapsulación siempre va del emisor al receptor.

¿Por qué KEM y no cifrado directo?

La decisión de NIST de estandarizar KEMs en lugar de PKE (cifrado asimétrico directo) responde a:

Simplicidad: Un KEM tiene una interfaz más pequeña y menos modos de fallo.
Híbrido natural: Kyber + AES/ChaCha = cifrado híbrido, que es la práctica recomendada incluso con RSA/ECC.
FO transform manejable: La transformación de Fujisaki-Okamoto de un PKE a un KEM CCA-secure es más fácil de analizar y verificar que un PKE CCA-secure directo.

Para cifrado asimétrico de propósito general, se usa HPKE (Hybrid Public Key Encryption, RFC 9180), que define cómo combinar un KEM con un AEAD. HPKE con Kyber ya está siendo estandarizado.

Referencias

Fujisaki, E. & Okamoto, T. (1999). "Secure Integration of Asymmetric and Symmetric Encryption Schemes." CRYPTO 1999.
Hofheinz, D., Hövelmanns, K. & Kiltz, E. (2017). "A Modular Analysis of the Fujisaki-Okamoto Transformation." TCC 2017.
RFC 9180 — Hybrid Public Key Encryption (HPKE).

Estructura del KEMEstructura del KEM