Modern cryptographic systems are not built around encrypting messages directly with public keys. Instead, they are built around establishing secrets. Once a shared secret exists, symmetric cryptography takes over, handling confidentiality, integrity, and authentication efficiently at scale.

This design choice is not an accident. It reflects both performance constraints and deep cryptographic realities. Public-key cryptography is expensive and assumption-heavy. Symmetric cryptography is fast, robust, and conservative. The role of public-key cryptography is therefore reduced to a single task: securely establishing a shared secret.

This task is formalized by the notion of a Key Encapsulation Mechanism (KEM).

What Is a Key Encapsulation Mechanism (KEM)?

A Key Encapsulation Mechanism is a cryptographic primitive whose purpose is not to encrypt arbitrary messages, but to securely deliver a randomly generated symmetric key from one party to another.

A KEM is defined by three algorithms:

• KeyGen

• Encaps

• Decaps

Each algorithm plays a precise role, and none of them can be removed without breaking the abstraction.

Key Generation

In the key generation phase, a user—let’s call her Alice—generates a key pair:

• a public encapsulation key ek

• a private decapsulation key dk

The encapsulation key is meant to be distributed freely. It may be embedded in certificates, posted on servers, or hardcoded into protocols. The decapsulation key must remain secret.

At this stage, no shared secret exists yet. The key pair merely enables someone else to establish one later.

Encapsulation

Encapsulation is performed by another party—let’s call him Bob.

Using Alice’s public encapsulation key, Bob:

1. Generates a fresh, uniformly random symmetric key $K$

2. Produces a ciphertext $c$ that encapsulates this key

3. Sends only $c$ to Alice

The key $K$ is not transmitted, encrypted, or revealed in any explicit way. It exists only implicitly through the cryptographic structure of $c$.

This design ensures that:

• even if ciphertexts are public,

• even if they are stored indefinitely,

• the key remains indistinguishable from random to any attacker.

Decapsulation

Using her private decapsulation key, Alice processes the ciphertext $c$ and deterministically recovers the same symmetric key $K$.

At this point:

• Alice and Bob share a secret

• no further public-key operations are needed

• symmetric cryptography can be used for all subsequent communication

Why Existing KEMs Are Not Post-Quantum Secure?

Most deployed KEMs today are based on classical hardness assumptions:

• RSA-based KEMs rely on integer factorization

• Diffie–Hellman KEMs rely on discrete logarithms

• Elliptic-curve KEMs rely on elliptic-curve discrete logarithms

All of these assumptions are broken by Shor’s algorithm.

Harvest Now, Decrypt Later

The most dangerous aspect of quantum attacks is not future communication—it is past communication.

An adversary can:

1. Passively record encrypted traffic today

2. Store ciphertexts indefinitely

3. Decrypt everything once quantum capabilities exist

This attack model is known as harvest-now, decrypt-later.

Importantly:

• the attacker does not need to interact with the protocol

• the attacker does not need to break keys today

• the attacker only needs storage and patience

---

Kyber: A Post-Quantum Secure KEM

Kyber is a lattice-based KEM standardized by NIST as FIPS-203 (ML-KEM).

Its security is based on the Module-Learning With Errors (Module-LWE) problem, a generalization of LWE that balances efficiency and security.

It follows a clean structure:

1. Define a lattice-based public-key encryption scheme (Kyber-PKE)

2. Apply the Fujisaki–Okamoto transform

3. Obtain a CCA-secure KEM

Mathematical Setting and Parameters

Kyber operates over the polynomial ring:

$$R_q = \mathbb{Z}_q[X]/(X^n + 1)$$

For ML-KEM-768, the parameters are:

• \(q=3329\)

• \(n=256\)

• \(k = 3\)

• noise parameters \(\eta_1 = 2, \eta_2 = 2\)

• compression parameters \(d_u = 10, d_v = 4\)

Kyber-PKE Key Generation

Alice performs the following steps:

1. Sample a random seed \(ρ∈\{0, 1\}^{256}\)

2. Deterministically expand $ρ$ into a matrix

$$A \in R_q^{k \times k}$$

3. Sample secret vector \(s \in R_q^k\) from a centered binomial distribution

4. Sample error vector \(e \in R_q^k\) from the same distribution

5. Compute

$$t = As + e$$

The keys are:

• public key: $(ρ, t)$

• secret key: $s$

Alice’s goal here is to create a sort of mathematical "locked box." By expanding a random seed into a matrix $A$ and generating a secret vector $s$, she sets the stage for a Module-LWE instance. The critical step is adding the error vector $e$. This tiny bit of noise is what makes the system secure; without it, an attacker could use simple linear algebra to solve for $s$. Instead, they are left with \(t = As + e\), a result that looks like random noise but secretly hides Alice's private key.

Kyber-PKE Encryption

To encrypt a message \(m \in \{0, 1 \}^n\), Bob:

1. Reconstructs $A$ from \(\rho\).

2. Samples randomness

   1. \(r \sim \chi_{\eta_1}^k\)

   2. \(e_1 \sim \chi_{\eta_2}^k\)

   3. \(e_2 \sim \chi_{\eta_1}\)

3. Computes:

$$u = A^Tr + e_1$$

$$v = t^Tr + e_2 + \Bigl\lfloor\frac{q}{2}\Bigr\rfloor m$$

4. Calculates \(c_1\) by compressing $u$ to \(d_u \) bits.

5. Calculates \(c_2\) by compressing $v$ to \(d_v \) bits.

6. Outputs ciphertext \(c = (c_1, c_2)\).

Kyber-PKE Decryption and Correctness

Alice:

1. Decompresses $u$ and $v$.

2. Computes:

$$v - s^Tu$$

3. Substituting definitions:

$$v - s^T u = t^T r + e_2 + \Bigl\lfloor\frac{q}{2}\Bigr\rfloor m - s^T(A^T r + e_1)$$

4. Using \(t = As + e\):

$$= r^T A s + r^T e + e_2 + \Bigl\lfloor\frac{q}{2}\Bigr\rfloor m - r^T A s - s^T e_1$$

$$= r^T e + e_2 - s^T e_1 + \Bigl\lfloor\frac{q}{2}\Bigr\rfloor m$$

When she computes \(v - s^T u\), the terms involving the matrix $A$ cancel out perfectly, leaving her with the scaled message plus a small pile of accumulated noise: \(r^Te + e_2 - s^Te_1\). Because this noise is small relative to the scaling factor, Alice can simply round the result to the nearest bit, effectively "shaking off" the errors to reveal Bob’s original message $m$.

From Kyber-PKE to Kyber-KEM

Now, let’s see how we can construct Kyber-KEM by utilizing the Kyber-PKE primitives!

Kyber-KEM Key Generation

Alice:

1. Runs Kyber-PKE.KeyGen → \(((\rho, t), s)\).

2. Samples a random value \(z \in \{ 0, 1 \}^{256}\).

3. Sets:

   • encapsulation key: \(ek = (\rho, t)\)

   • decapsulation key:

$$dk = (s, ek, H(ek), z)$$

Kyber-KEM Encapsulation

Bob:

1. Obtains authentic $ek$.

2. Selects:

$$m \in \{0, 1\}^{256}$$

3. Computes:

$$h = H(ek)$$

$$(K, R) = G(m, h)$$

with $H$ and $G$ being some hash functions.

4. Uses Kyber-PKE.Enc to compute

$$c = PKE.Enc_{ek}(m; r)$$

5. Outputs the secret key $K$ and ciphertext $c$.

Kyber-KEM Decapsulation

To recover the secret key $K$ from $c$ using decapsulation key $dk$, Alice does:

1. Use the Kyber-PKE to compute \(PKE.Dec_s(c)\) and call it the plaintext $m'$.

2. Compute:

$$(K', R') = G(m', H(ek))$$

1. Compute fallback \(\bar{K} = J(z, c)\) with J being a hash function.

2. Compute:

$$PKE.Enc_{ek}(m') = c'.$$

1. If \(c \neq c'\), then return \(\bar{K}\).

2. Otherwise, return $K'$.

In Kyber-KEM Decapsulation, Alice doesn't just trust the recovered message $m'$. She actually re-encrypts it to see if it produces the exact same ciphertext Bob sent. If even a single bit differs (\(c \neq c'\)), she knows the ciphertext was tampered with and returns a random "fallback" value instead.

---

Conclusion

The transition to post-quantum cryptography is a practical necessity, especially in the blockchain setting where almost everything as public forever. As we have seen, the security of our current digital infrastructure rests on assumptions—like the hardness of integer factorization or discrete logarithms—that will not hold in a quantum future. Kyber, now officially standardized as ML-KEM by NIST in FIPS 203, represents the most mature and efficient path forward for general-purpose encryption.

As these algorithms begin to integrate into our systems, they will provide the necessary security to protect our data against the potential threats posed by quantum computers. This shift is crucial to ensure that our digital communications remain secure in the face of advancing technology.

Further Reading & Resources

If you want to dive deeper into the world of lattice-based cryptography and the official standards, here are some of the best places to start:

1. The Official Standard

• NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard The definitive technical document for ML-KEM (formerly Kyber), covering the precise mathematical specifications and parameter sets like ML-KEM-768.

2. Lattice Math & LWE Tutorials

• Learning with Errors (LWE) Survey by Oded Regev A foundational paper by the creator of LWE, explaining why adding noise to linear equations makes them so hard to solve.

• A Simple Lattice-Based Encryption Scheme A great "from scratch" walkthrough that builds a simplified version of the math used in Kyber to help you visualize the noise and rounding process.

3. Understanding the FO Transform

• The Fujisaki-Okamoto Transformation Revisited A deep dive into how we turn "weak" encryption into "strong" KEMs through re-encryption checks and hashing.

4. Implementation in the Wild

• PQXDH: Signal's Post-Quantum Protocol Learn how Signal integrated Kyber into their protocol to protect over a hundred million users from future quantum threats.