Inside CRYSTALS-Kyber: How Lattice-Based Cryptography Works
A practitioner's walkthrough of Kyber — the cryptographic substrate of the post-quantum era. No PhD required. We promise.
CRYSTALS-Kyber became the NIST standard for general-purpose post-quantum key encapsulation in 2024, codified as FIPS 203 (also called ML-KEM). It now sits at the heart of every TLS handshake we deploy at LumixSys. If you operate production systems, you'll be reading 'Kyber-1024' in change tickets for the next decade — so let's make sure you can read it confidently.
Why lattices?
Lattice problems give us cryptographic hardness that survives quantum attack. The specific hard problem behind Kyber is called Module Learning With Errors (MLWE). Informally: given a noisy linear system over a structured ring, recover the secret. Classical algorithms cannot do this efficiently. As of 2026, neither can quantum algorithms — and there is no efficient quantum reduction known for any variant of LWE.
An intuition pump
Picture a 2D lattice as a grid of dots. Give someone a vector that lands near a lattice point but slightly off. Their job is to find the closest lattice point. In two dimensions, this is easy. In 256 dimensions with the right parameters, the best known algorithms are subexponential. That gap is your security margin.
Kyber, in pieces
Kyber is a Key Encapsulation Mechanism (KEM), not a generic encryption scheme. It is designed to exchange a small symmetric key that you'll then use with AES-GCM or ChaCha20-Poly1305 for bulk data. The KEM has three operations:
- 1KeyGen(): produce a public/private keypair.
- 2Encaps(pk): given a public key, produce a ciphertext and a shared secret.
- 3Decaps(sk, c): given the private key and ciphertext, recover the shared secret.
There are three parameter sets: Kyber-512, Kyber-768, and Kyber-1024 — corresponding (loosely) to AES-128, AES-192, and AES-256 security levels. For long-term-confidentiality workloads we deploy Kyber-1024.
The hybrid mode you should use today
Nobody — not us, not NIST, not the IETF — recommends running 'pure' Kyber in production yet. The standard is hybrid: X25519 + Kyber-1024 in TLS 1.3. The shared secret is the concatenation of both KEMs' outputs, fed into the standard HKDF. If either algorithm fails, you still have the other.
$ openssl s_client -connect lumixsys.com:443 -groups X25519MLKEM768
...
Negotiated group: X25519MLKEM768
Cipher: TLS_AES_256_GCM_SHA384Performance — where the surprises hide
Kyber is fast. On a modern x86 chip with AVX2, Kyber-1024 Encaps runs in ~25 microseconds. The interesting cost is bandwidth: Kyber's public keys and ciphertexts are roughly 1.5KB and 1.6KB respectively. For a single handshake, that's noise. For a service mesh doing 500K handshakes per second, it's an extra 1.5GB/s of east-west traffic.
What can go wrong
Three failure modes haunt every Kyber deployment we've debugged:
- Implementation side-channels. Kyber's reference implementations are constant-time on x86 — most ports to embedded targets are not.
- RNG misuse. Kyber is sensitive to noise sampling. A bad PRNG silently breaks IND-CCA2 security.
- Crypto-agility gaps. Hard-coded Kyber-1024 in 200 services means a 9-month migration if NIST publishes an updated parameter set.