ImplementationImplementation

Summary

Kyber is designed to be implemented efficiently both in software and hardware. Its main operations are polynomial multiplications in R_q = Z_q[x]/(x^n + 1) with n = 256, q = 3329.

NTT — Number Theoretic Transform

Multiplication in R_q is the dominant operation. Kyber accelerates it using NTT, the analog of FFT in finite fields.

Naive multiplication: O(n²) = 65,536 operations
Multiplication via NTT: O(n log n) ≈ 2,048 operations

The NTT in Kyber uses primitive roots of unity in Z_q. Since q = 3329 is prime and 3329 ≡ 1 (mod 512), there exists a primitive root of order 512, necessary for NTT with n = 256.

The Transform

Kyber does not NTT-transform all polynomials. A key optimization is to keep some polynomials in NTT domain (already transformed) to avoid unnecessary transformations:

• Â (the transformed public matrix) is stored in NTT domain
• ŝ (the transformed secret key) is also stored in NTT domain
• Encapsulation requires transforming s' to NTT domain and transforming u back

This reduces the number of inverse NTT operations needed.

Compress and Decompress

Kyber compresses ciphertexts by discarding low-magnitude bits. This reduces the size of ct but introduces compression error — error that adds to the cryptographic error and must be handled by the parameters.

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

Where d controls precision: more bits → less compression error → larger ciphertext.

Compression is not symmetric: Decompress(Compress(x)) ≈ x but not equal. The difference must be absorbed by the scheme's error margin.

FO Transform — Fujisaki-Okamoto

The FO transform is what converts a PKE (asymmetric encryption) insecure against adaptive attacks into a CCA-secure KEM.

Kyber's underlying PKE (without FO) is CPA-secure but not CCA-secure. Without FO, an attacker could:

1. Intercept a ciphertext ct
2. Modify it slightly → ct'
3. Observe whether the receiver accepts ct' or not (validity oracle)
4. Use that information to recover the key

FO eliminates this by having the decryption reprocess the received ciphertext and verify that it matches the one that would be generated from scratch with the same random coin. If it does not match, a pseudorandom key is returned (not the real one).

Implicit vs Explicit FO

Kyber uses implicit FO: it does not return a distinguishable rejection symbol, but a fake key. This avoids oracle attacks that depend on distinguishing "failure" from "success."

Decaps(sk, ct):
    m' = Decrypt(sk, ct)          # decrypt
    (K', r') = G(m' || H(pk))     # reprocess
    ct' = Encrypt(pk, m', r')     # re-encrypt
    if ct' == ct:
        return K'                 # real
    else:
        return H(sk || ct)        # pseudorandom (indistinguishable)

Deterministic Sampling of A

The matrix A is generated from a seed d using SHAKE-128 as an extendable output function (XOF). This means:

1. A does not need to be stored in the public key (only the seed is stored, 32 bytes).
2. Anyone can reconstruct A knowing the seed.
3. Generation is deterministic: same seed → same matrix.

The seed is included in pk as part of the 800/1184/1568 bytes.

Optimizations

Software

Hardware

Reference Implementations

References

• 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.