CRYSTALS-Kyber:
Quantum-Safe Key Encapsulation Explained

Every secure connection on the internet begins with a key agreement. When you visit a website over HTTPS, your browser and the server must agree on a shared secret key that encrypts the session. Today, this is accomplished with X25519 or ECDH—elliptic curve protocols that rely on the difficulty of the discrete logarithm problem. A sufficiently powerful quantum computer running Shor's algorithm would solve that problem in polynomial time, breaking every key exchange that has ever occurred.

CRYSTALS-Kyber, standardized by NIST as ML-KEM (Module Lattice-Based Key Encapsulation Mechanism) in FIPS 203, is the algorithm selected to replace those vulnerable protocols. It is already deployed in Chrome, Cloudflare, AWS, and Signal. It is fast, compact enough for real-world use, and built on mathematical foundations that quantum computers cannot efficiently attack.

This article covers the full depth of Kyber: what key encapsulation actually is, the lattice mathematics underneath, NIST parameter sets and their trade-offs, performance characteristics on production hardware, the TLS 1.3 hybrid deployment model, real-world adoption, CNSA 2.0 compliance deadlines, and H33's production usage in the OCR encrypt/decrypt pipeline.

What Is Key Encapsulation (and Why It Replaced Key Exchange)

Before understanding Kyber, you need to understand why the cryptographic community moved from key exchange to key encapsulation—and why this distinction matters for post-quantum security.

Traditional Key Exchange: Diffie-Hellman

In classical Diffie-Hellman (DH) key exchange, both parties contribute equally to the shared secret. Alice picks a secret a, Bob picks a secret b, and they exchange g^a mod p and g^b mod p. Both can then compute g^(ab) mod p—the shared secret—without ever transmitting it. The security relies on the assumption that computing discrete logarithms is hard.

Elliptic curve Diffie-Hellman (ECDH) and X25519 use the same principle on elliptic curve groups: Alice and Bob each pick scalar multipliers, exchange curve points, and derive a shared secret. The security relies on the elliptic curve discrete logarithm problem (ECDLP).

Both DH and ECDH are interactive key exchange protocols: the two parties perform symmetric operations to jointly derive a secret. This is elegant, but it has a structural problem in the post-quantum world.

Why KEM Replaced Key Exchange

Lattice-based cryptography does not naturally produce the kind of symmetric, commutative structure that Diffie-Hellman exploits. There is no lattice analogue of g^(ab) = g^(ba). Attempts to construct lattice-based key exchange protocols directly have been fragile, requiring careful noise management and often leaking information through approximate agreement.

A Key Encapsulation Mechanism (KEM) sidesteps this entirely. Instead of both parties contributing to a shared secret, one party generates the secret and encapsulates it under the other party's public key:

The result is identical to key exchange: both parties share a 32-byte secret ss that can be used as an AES or ChaCha20 session key. But the KEM construction is asymmetric by design—Bob generates the secret and encapsulates it, Alice recovers it. This asymmetry maps naturally onto lattice-based cryptography and avoids the fragile noise-matching problems of direct key exchange.

From a protocol perspective, KEM is a drop-in replacement for key exchange. TLS 1.3 was designed to accommodate KEMs without protocol changes: the client sends a KEM public key in its ClientHello, and the server responds with the ciphertext in its ServerHello. The shared secret feeds into the TLS key schedule identically to how an ECDH shared secret would.

How CRYSTALS-Kyber Works

Kyber's security is based on the Module Learning With Errors (Module-LWE) problem, a structured variant of the Learning With Errors (LWE) problem that has been studied extensively in lattice cryptography since Oded Regev's foundational 2005 paper. The "Module" prefix indicates that Kyber works over modules (vectors of polynomial ring elements) rather than individual integers or single polynomials, hitting a practical sweet spot between the generality of standard LWE and the efficiency of Ring-LWE.

The Module-LWE Problem

The core hardness assumption is this: given a random matrix A over the polynomial ring R_q = Z_q[X]/(X^n + 1) with n = 256 and q = 3329, and a vector b = As + e where s is a secret vector and e is a small error vector drawn from a centered binomial distribution, it is computationally infeasible to recover s.

This problem remains hard even for quantum computers. Unlike integer factorization or discrete logarithms, there is no known quantum algorithm that solves Module-LWE in polynomial time. The best known attacks (both classical and quantum) are lattice reduction algorithms whose complexity grows exponentially with the security parameter.

Kyber's Three Algorithms

Kyber defines three algorithms that compose the KEM:

The Number Theoretic Transform (NTT)

The computationally dominant operation in Kyber is polynomial multiplication in the ring R_q. Naive polynomial multiplication is O(n^2), which at n = 256 would be prohibitively slow. Kyber uses the Number Theoretic Transform (NTT)—essentially a Fast Fourier Transform over a finite field—to reduce polynomial multiplication to O(n log n).

The NTT converts polynomials from coefficient representation to evaluation representation (the "NTT domain"), where polynomial multiplication becomes element-wise multiplication. Two forward NTTs, one pointwise multiplication, and one inverse NTT replace what would otherwise be 65,536 multiply-accumulate operations with roughly 3,000.

The choice of q = 3329 is deliberate: it is prime, and 3329 = 13 * 256 + 1, meaning q ≡ 1 (mod 2n). This guarantees the existence of primitive 2n-th roots of unity in Z_q, which the NTT requires. Kyber uses a "negacyclic" NTT variant that maps the ring Z_q[X]/(X^256 + 1) to 128 degree-1 quotient rings, enabling the full polynomial multiplication in NTT domain.

The CCA Transform (Fujisaki-Okamoto)

Kyber's underlying public-key encryption scheme (CPAPKE) is only IND-CPA secure—it resists chosen-plaintext attacks but not chosen-ciphertext attacks. In the real world, an adversary can submit maliciously crafted ciphertexts to a decryption oracle and learn information about the secret key.

The Fujisaki-Okamoto (FO) transform upgrades IND-CPA security to IND-CCA2 (adaptive chosen-ciphertext) security. It works by making encryption deterministic (deriving all randomness from the message and public key hash) and adding an implicit rejection mechanism: if decapsulation detects a tampered ciphertext (by re-encrypting and comparing), it returns a pseudorandom value indistinguishable from a real shared secret. This prevents the adversary from learning anything useful from decryption failures.

The FO transform is critical for real-world security. Without it, subtle decryption failures could be exploited in active attacks against TLS sessions. With it, Kyber achieves IND-CCA2 security—the strongest standard notion of public-key encryption security.

FIPS 203 ML-KEM Parameter Sets

NIST standardized three parameter sets for ML-KEM, corresponding to three security levels. The primary parameters that change are k (the module dimension—how many polynomial ring elements form each vector), the noise distribution width, and the compression parameters for ciphertexts.

ML-KEM-768 is the recommended parameter set for most applications. It provides NIST Security Level 3 (roughly equivalent to AES-192), which exceeds the 128-bit post-quantum security threshold with a comfortable margin. ML-KEM-512 is faster and smaller but offers only Level 1 security, which some organizations consider insufficient for long-term protection. ML-KEM-1024 provides Level 5 (AES-256 equivalent) but with proportionally larger keys and ciphertexts.

Key Sizes and Ciphertext Sizes vs. Classical Algorithms

The most visible trade-off for post-quantum security is larger keys and ciphertexts. Here is how ML-KEM compares to the algorithms it replaces:

ML-KEM-768 adds roughly 2.2 KB to the TLS handshake compared to X25519 alone. In the hybrid configuration (X25519 + ML-KEM-768), the total is about 2.3 KB. On modern networks, this is negligible—well within a single TCP initial congestion window (typically 10 packets / ~14 KB). The shared secret remains a compact 32 bytes in all cases, so subsequent symmetric encryption is completely unaffected.

Performance Benchmarks

ML-KEM is exceptionally fast—often faster than the classical algorithms it replaces. Our February 2026 benchmarks on production hardware:

Graviton4 (AWS c8g.metal-48xl, Neoverse V2, 192 vCPUs)

ML-KEM-768 is 2.5x faster than X25519 for a complete key agreement flow and over 1,600x faster than RSA-2048. With H33's key pool architecture (pre-generating key pairs during idle periods), the effective keygen cost drops to 0.42 µs—a 79x speedup that enables 152 million operations per second on a single 64-core node.

The NTT-based arithmetic at n = 256 and q = 3329 fits entirely in L1 cache (256 coefficients × 2 bytes = 512 bytes per polynomial), which is why Kyber's computational performance is so strong. Elliptic curve operations, by contrast, require multi-precision integer arithmetic with carries that pipeline poorly on modern superscalar processors.

Why Kyber Won the NIST Competition

NIST's Post-Quantum Cryptography standardization process began in 2016 and received 69 initial submissions for key encapsulation mechanisms and digital signatures. After three rounds of evaluation spanning eight years, Kyber was the sole KEM selected for standardization in the initial announcement (August 2024). Understanding why requires examining what NIST was optimizing for.

The Selection Criteria

Kyber's main competitors in the final round were NTRU (lattice-based, but with a more complex algebraic structure), SABER (also Module-LWE but using power-of-two moduli instead of NTT-friendly primes), and Classic McEliece (code-based, with excellent security confidence but 261 KB public keys). Kyber won on the combined metric: it had the best overall package of security, speed, and compactness.

TLS 1.3 Hybrid Key Exchange

The dominant deployment model for ML-KEM today is hybrid key exchange, where the TLS handshake performs both a classical X25519 key exchange and an ML-KEM-768 encapsulation, then combines both shared secrets into the final session key.

Why Hybrid?

Hybrid mode provides defense in depth: the session is secure if either algorithm holds. If a breakthrough breaks lattice problems (extremely unlikely but theoretically possible), X25519 still protects the session. If a quantum computer breaks X25519, ML-KEM still protects the session. You only lose confidentiality if both algorithms are broken simultaneously.

This is not mere conservatism. ML-KEM has been studied for decades in academic settings but has only been deployed at internet scale since 2023. Hybrid mode allows the industry to gain deployment experience with a safety net.

How It Works in TLS 1.3

// Client generates both key shares
ClientHello:
  supported_groups: [x25519_mlkem768]     // hybrid group ID
  key_share:
    x25519_pk:  32 bytes                  // X25519 public key
    mlkem768_pk: 1,184 bytes              // ML-KEM-768 public key

// Server performs both operations
ServerHello:
  key_share:
    x25519_pk:  32 bytes                  // X25519 public key
    mlkem768_ct: 1,088 bytes              // ML-KEM-768 ciphertext

// Both parties derive the combined shared secret
let ss_ecdh  = x25519(client_sk, server_pk);    // 32 bytes
let ss_mlkem = mlkem_decaps(client_sk, ct);     // 32 bytes
let combined = concat(ss_ecdh, ss_mlkem);       // 64 bytes
let session_key = HKDF(combined);              // Into TLS key schedule

The total additional data in the handshake is approximately 2.3 KB (1,184 bytes for the ML-KEM public key in ClientHello and 1,088 bytes for the ciphertext in ServerHello). The cryptographic overhead on the server side is ~18 µs for encapsulation—invisible compared to the network round-trip time.

Real-World Deployment

ML-KEM hybrid key exchange is no longer experimental. It is deployed at massive scale across the internet's core infrastructure.

Google Chrome and Chromium

Chrome enabled X25519 + Kyber-768 hybrid key exchange by default starting in Chrome 124 (April 2024). As of February 2026, Chrome performs hybrid post-quantum key exchange on every TLS 1.3 connection to servers that support it. Given Chrome's ~65% browser market share, this means a majority of web traffic is already protected against harvest-now-decrypt-later attacks on the key exchange layer.

Cloudflare

Cloudflare enabled post-quantum key exchange across its entire edge network in 2023, initially with X25519Kyber768Draft00 and transitioning to the final FIPS 203 ML-KEM-768 after standardization. Cloudflare's network handles approximately 20% of all HTTP traffic globally. Their deployment data confirmed that the 2.3 KB handshake overhead has no measurable impact on connection latency on broadband connections and a negligible impact (<5 ms) even on constrained mobile networks.

AWS

AWS Key Management Service (KMS) and AWS Certificate Manager support ML-KEM for TLS connections. AWS's s2n-tls library (their TLS implementation) includes ML-KEM-768 hybrid support, and AWS has published guidance recommending migration to hybrid PQC TLS for all production workloads.

Signal

Signal Protocol integrated Kyber into its X3DH key agreement protocol (renamed PQXDH) in September 2023. Every new Signal session now includes a Kyber-1024 key encapsulation alongside the classical X25519 exchange, protecting message confidentiality against future quantum decryption.

Other Deployments

• Apple iMessage: PQ3 protocol uses Kyber-1024 for initial key establishment and periodic rekeying
• Mullvad VPN: Post-quantum WireGuard tunnels using ML-KEM
• OpenSSH 9.x: Support for hybrid ML-KEM-768 + X25519 key exchange
• Firefox: ML-KEM hybrid support enabled in Nightly, staged rollout to stable

CNSA 2.0 Deadlines for Key Establishment Migration

The NSA's Commercial National Security Algorithm Suite 2.0 (September 2022) sets hard deadlines for post-quantum migration in national security systems. For key establishment (the domain ML-KEM addresses), the deadlines are:

CNSA 2.0 specifies ML-KEM-1024 (not ML-KEM-768) for national security systems, reflecting the NSA's conservative posture on key establishment for classified data. For commercial applications, ML-KEM-768 is the standard recommendation. See the full government compliance timeline for federal procurement deadlines.

Beyond CNSA 2.0, NIST IR 8547 (November 2024) establishes the broader federal timeline: all classical public-key cryptography (RSA, ECDH, ECDSA) will be deprecated after 2030 and disallowed in federal systems after 2035. Private-sector organizations that handle federal data or participate in federal supply chains should plan accordingly.

H33's Kyber Usage: The OCR Encrypt/Decrypt Pipeline

H33 uses CRYSTALS-Kyber in production for the OCR encrypt/decrypt pipeline—the system that secures optical character recognition data (document scans, ID images, sensitive text extractions) with post-quantum end-to-end encryption.

Architecture

The OCR pipeline uses a three-layer cryptographic stack:

1. Kyber (ML-KEM-768): Key encapsulation to establish a per-document shared secret between the client and H33's processing infrastructure
2. AES-256-GCM: Symmetric encryption of the OCR payload using the Kyber-derived shared secret
3. Dilithium (ML-DSA-65): Digital signature over the ciphertext for integrity and non-repudiation

This combination—Kyber for key establishment, AES-256 for bulk encryption, Dilithium for authentication—provides a fully post-quantum secure pipeline. Every component is resistant to both classical and quantum attacks.

use crate::pqc::kyber::{KyberKeypair, encapsulate, decapsulate};
use crate::pqc::dilithium::{sign, verify};
use aes_gcm::{Aes256Gcm, Key, Nonce};

/// Encrypt an OCR document with post-quantum security.
/// Kyber KEM establishes the session key; AES-256-GCM encrypts the payload;
/// Dilithium signs the ciphertext bundle for integrity.
pub fn ocr_encrypt(
    plaintext: &[u8],
    recipient_pk: &KyberPublicKey,
    signer_sk: &DilithiumSecretKey,
) -> OcrCiphertext {
    // Step 1: Kyber encapsulation — derive 32-byte shared secret
    let (ciphertext_kem, shared_secret) = encapsulate(recipient_pk);

    // Step 2: AES-256-GCM encryption using Kyber-derived key
    let key = Key::from_slice(&shared_secret);
    let nonce = generate_nonce();  // 96-bit random
    let ciphertext_aes = Aes256Gcm::new(key)
        .encrypt(&nonce, plaintext)
        .expect("AES-GCM encryption");

    // Step 3: Dilithium signature over the full bundle
    let bundle = concat_bundle(&ciphertext_kem, &nonce, &ciphertext_aes);
    let signature = sign(signer_sk, &bundle);

    OcrCiphertext { ciphertext_kem, nonce, ciphertext_aes, signature }
}

/// Decrypt an OCR document — verify signature, decapsulate, then AES-GCM decrypt.
pub fn ocr_decrypt(
    ct: &OcrCiphertext,
    recipient_sk: &KyberSecretKey,
    signer_pk: &DilithiumPublicKey,
) -> Result<Vec<u8>, OcrError> {
    // Step 1: Verify Dilithium signature
    let bundle = concat_bundle(&ct.ciphertext_kem, &ct.nonce, &ct.ciphertext_aes);
    verify(signer_pk, &bundle, &ct.signature)?;

    // Step 2: Kyber decapsulation — recover 32-byte shared secret
    let shared_secret = decapsulate(recipient_sk, &ct.ciphertext_kem)?;

    // Step 3: AES-256-GCM decryption
    let key = Key::from_slice(&shared_secret);
    let plaintext = Aes256Gcm::new(key)
        .decrypt(&Nonce::from_slice(&ct.nonce), ct.ciphertext_aes.as_ref())?;

    Ok(plaintext)
}

The Kyber encapsulation adds ~18 µs to the encrypt path and ~55 µs to the decrypt path. For OCR workloads where the AES-256-GCM encryption of the document payload itself takes hundreds of microseconds to milliseconds (depending on document size), the Kyber overhead is negligible.

Common Misconceptions About KEM vs. Diffie-Hellman

The shift from key exchange to key encapsulation has generated confusion in the developer community. Here are the most common misconceptions and their corrections.

Misconception 1: "KEM is less secure than Diffie-Hellman"

This is backwards. KEM with a CCA-secure scheme like ML-KEM provides stronger security guarantees than basic Diffie-Hellman. The FO transform gives ML-KEM IND-CCA2 security—it resists active chosen-ciphertext attacks. Standard ECDH provides only passive security unless wrapped in a signed protocol (like TLS with server authentication). The KEM construction forces CCA security by design.

Misconception 2: "KEM doesn't provide forward secrecy"

Forward secrecy depends on ephemeral key generation, not on the key agreement mechanism. In TLS 1.3, the client generates a fresh ML-KEM key pair for every handshake. After the session key is derived and the handshake completes, the ephemeral ML-KEM secret key is erased. Compromising long-term keys (like server authentication keys) does not expose past session keys. ML-KEM provides forward secrecy in exactly the same way ephemeral ECDH does.

Misconception 3: "The asymmetry of KEM means the server controls the secret"

In TLS 1.3 with ML-KEM, the client generates the KEM key pair (in ClientHello) and the server encapsulates. The server "chooses" the shared secret in the sense that Encaps generates it, but the shared secret is derived from both the server's randomness and the client's public key. Neither party unilaterally controls the session key. Additionally, the session key is derived via HKDF from the KEM shared secret combined with handshake transcript hashes, ensuring both parties' contributions are incorporated.

Misconception 4: "Post-quantum key sizes make Kyber impractical"

As demonstrated by Chrome, Cloudflare, and AWS deployments at internet scale, ML-KEM-768's 2.3 KB handshake overhead has no measurable impact on connection establishment latency on modern networks. The sizes are larger than X25519 (by ~2.2 KB), but they are far smaller than many web assets transferred on every page load. This misconception persists from early post-quantum research when key sizes for some candidates (like Classic McEliece at 261 KB) were genuinely problematic.

Misconception 5: "You should wait for HQC before deploying"

HQC (Hamming Quasi-Cyclic) is NIST's backup KEM candidate from a different mathematical family (code-based rather than lattice-based). Its standardization is expected around 2027. Waiting for HQC before deploying ML-KEM means years of unnecessary exposure to harvest-now-decrypt-later attacks. ML-KEM is standardized, battle-tested at scale, and available today. Deploy ML-KEM now. If HQC proves useful later, it can be added as an additional option.

Implementation Guidance

For teams integrating ML-KEM into production systems, here are the critical implementation considerations.

Use Established Libraries

Do not implement ML-KEM from scratch. The algorithm involves subtle constant-time requirements (NTT, CBD sampling, FO comparison) where implementation errors create side-channel vulnerabilities. Use one of these vetted implementations:

• liboqs (Open Quantum Safe): C library, the reference implementation used by most integrations
• pqcrypto-kyber (Rust): Rust bindings to the reference C implementation
• aws-lc: AWS's libcrypto fork with ML-KEM support, used in s2n-tls
• BoringSSL: Google's fork, powers Chrome's ML-KEM deployment
• H33 SDK: Integrated ML-KEM with FHE and ML-DSA in a single API, available for Rust, Python, TypeScript, and Go

Always Use Hybrid Mode (For Now)

Deploy ML-KEM in hybrid mode (X25519 + ML-KEM-768 for TLS, or the equivalent for your protocol). Hybrid mode is recommended by NIST, NSA, BSI (Germany), ANSSI (France), and NCSC (UK). It provides safety against both classical and quantum attacks, plus insurance against any unexpected breakthrough in lattice cryptanalysis.

Handle Decapsulation Failures Correctly

ML-KEM's FO transform uses implicit rejection: when decapsulation detects a tampered ciphertext, it returns a pseudorandom value rather than an error. This is essential for CCA security. Your code must never distinguish between a successful and "failed" decapsulation from the outside—both paths must take the same time and produce the same-length output. Established libraries handle this correctly. If you see an implementation that returns an error on decapsulation failure, it is broken.

Account for Key and Ciphertext Sizes in Protocols

If your protocol has fixed-size message fields, buffers, or MTU constraints, verify that ML-KEM-768's 1,184-byte public keys and 1,088-byte ciphertexts fit. Most modern protocols (TLS, QUIC, SSH) handle this gracefully, but custom binary protocols or constrained embedded systems may need buffer adjustments.

use h33::pqc::kyber::{Kyber768, keypair, encapsulate, decapsulate};

fn main() {
    // Alice generates a key pair
    let (alice_pk, alice_sk) = keypair::<Kyber768>();
    assert_eq!(alice_pk.as_bytes().len(), 1184);  // ML-KEM-768 public key

    // Bob encapsulates a shared secret under Alice's public key
    let (ciphertext, shared_secret_bob) = encapsulate(&alice_pk);
    assert_eq!(ciphertext.as_bytes().len(), 1088);  // ML-KEM-768 ciphertext
    assert_eq!(shared_secret_bob.len(), 32);         // 256-bit shared secret

    // Alice decapsulates to recover the same shared secret
    let shared_secret_alice = decapsulate(&alice_sk, &ciphertext);
    assert_eq!(shared_secret_alice, shared_secret_bob);

    // Both parties now share a 32-byte key for AES-256 / ChaCha20
    println!("Shared secret established: {} bytes", shared_secret_alice.len());
}

The Road Ahead

ML-KEM is the foundation of post-quantum key establishment, but the ecosystem continues to evolve.

HQC standardization (~2027): NIST selected HQC (Hamming Quasi-Cyclic) as a backup KEM based on code-based (not lattice-based) assumptions. If a catastrophic break in lattice problems is ever discovered, HQC provides an alternative from a completely different mathematical family. Its larger ciphertexts (~4,500 bytes for comparable security) make it less practical as a primary choice, but it serves as critical algorithmic diversity insurance.

ML-KEM in DNSSEC and certificate transparency: Ongoing work to integrate post-quantum key exchange into DNS security extensions and certificate transparency logs. These are critical infrastructure components where quantum vulnerability would have cascading effects.

Post-quantum VPN migration: WireGuard and IPsec working groups are standardizing ML-KEM-based key exchange for VPN tunnels. Mullvad and several enterprise VPN providers already offer experimental support.

NIST IR 8547 enforcement: The 2030 deprecation and 2035 disallowance deadlines for classical public-key cryptography in federal systems will drive the most massive cryptographic migration in history. Organizations that begin now will have a smooth transition. Those that wait will face emergency migrations under regulatory pressure.

H33 provides post-quantum infrastructure with ML-KEM key encapsulation, ML-DSA digital signatures, and FHE biometric processing—all in a single API call at sub-millisecond latency. Every component in the production stack is quantum-resistant by construction. The Kyber integration in our OCR encrypt/decrypt pipeline processes documents with ~18 µs encapsulation overhead and full Dilithium attestation.