ImplementaciónImplementación

Resumen

Kyber está diseñado para ser implementado eficientemente tanto en software como en hardware. Sus operaciones principales son multiplicaciones polinomiales en R_q = Z_q[x]/(x^n + 1) con n = 256, q = 3329.

NTT — Number Theoretic Transform

La multiplicación en R_q es la operación dominante. Kyber la acelera usando NTT, el análogo de la FFT en cuerpos finitos.

Multiplicación ingenua: O(n²) = 65,536 operaciones
Multiplicación vía NTT: O(n log n) ≈ 2,048 operaciones

El NTT en Kyber usa raíces primitivas de la unidad en Z_q. Como q = 3329 es primo y 3329 ≡ 1 (mod 512), existe una raíz primitiva de orden 512, necesaria para NTT con n = 256.

La Transformada

Kyber no NTT-transforma todos los polinomios. Una optimización clave es mantener algunos polinomios en dominio NTT (ya transformados) para evitar transformaciones innecesarias:

• Â (la matriz pública transformada) se almacena en dominio NTT
• ŝ (la clave secreta transformada) también se almacena en dominio NTT
• La encapsulación requiere transformar s' al dominio NTT y transformar de vuelta u

Esto reduce el número de NTT inversos necesarios.

Compress y Decompress

Kyber comprime los ciphertexts descartando bits de baja magnitud. Esto reduce el tamaño de ct pero introduce error de compresión — error que se suma al error criptográfico y debe ser manejado por los parámetros.

Compress_q(x, d) = ⌈(2^d / q) · x⌋ mod 2^d
Decompress_q(y, d) = ⌈(q / 2^d) · y⌋

Donde d controla la precisión: más bits → menos error de compresión → ciphertext más grande.

La compresión no es simétrica: Decompress(Compress(x)) ≈ x pero no igual. La diferencia debe ser absorbida por el margen de error del esquema.

FO Transform — Fujisaki-Okamoto

La transformación FO es lo que convierte un PKE (cifrado asimétrico) inseguro contra ataques adaptativos en un KEM CCA-secure.

El PKE subyacente de Kyber (sin FO) es CPA-secure pero no CCA-secure. Sin FO, un atacante podría:

1. Interceptar un ciphertext ct
2. Modificarlo ligeramente → ct'
3. Observar si el receptor acepta ct' o no (oráculo de validez)
4. Usar esa información para recuperar la clave

FO elimina esto haciendo que el descifrado reprocese el ciphertext recibido y verifique que coincide con el que se generaría desde cero con la misma moneda aleatoria. Si no coincide, se devuelve una clave pseudoaleatoria (no la real).

FO implícito vs explícito

Kyber usa FO implícito: no devuelve un símbolo de rechazo distinguible, sino una clave falsa. Esto evita ataques de oráculo que dependen de la distinción entre "fallo" y "éxito".

Decaps(sk, ct):
    m' = Decrypt(sk, ct)          # descifrar
    (K', r') = G(m' || H(pk))     # reprocesar
    ct' = Encrypt(pk, m', r')     # re-encifrar
    if ct' == ct:
        return K'                 # real
    else:
        return H(sk || ct)        # pseudoaleatorio (indistinguible)

Sampling Determinista de A

La matriz A se genera a partir de una semilla d usando SHAKE-128 como generador de números aleatorios extendible (XOF). Esto significa que:

1. A no necesita almacenarse en la clave pública (solo se almacena la semilla, 32 bytes).
2. Cualquiera puede reconstruir A conociendo la semilla.
3. La generación es determinista: misma semilla → misma matriz.

La semilla se incluye en pk como parte de los 800/1184/1568 bytes.

Optimizaciones

Software

Hardware

Implementaciones de Referencia

Referencias

• Bos, J. et al. (2018). "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM."
• Alkim, E. et al. (2020). "The Number Theoretic Transform and Its Applications in Lattice-Based Cryptography."
• Montgomery, P. (1985). "Modular Multiplication Without Trial Division." Mathematics of Computation.