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:
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:
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:
Generates a fresh, uniformly random symmetric key $K$
Produces a ciphertext $c$ that encapsulates this key
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:
Passively record encrypted traffic today
Store ciphertexts indefinitely
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:
Define a lattice-based public-key encryption scheme (Kyber-PKE)
Apply the Fujisaki–Okamoto transform
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:
Sample a random seed \(ρ∈\{0, 1\}^{256}\)
Deterministically expand $ρ$ into a matrix
$$A \in R_q^{k \times k}$$
Sample secret vector \(s \in R_q^k\) from a centered binomial distribution
Sample error vector \(e \in R_q^k\) from the same distribution
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:
Reconstructs $A$ from \(\rho\).
Samples randomness
\(r \sim \chi_{\eta_1}^k\)
\(e_1 \sim \chi_{\eta_2}^k\)
\(e_2 \sim \chi_{\eta_1}\)
Computes:
$$u = A^Tr + e_1$$
$$v = t^Tr + e_2 + \Bigl\lfloor\frac{q}{2}\Bigr\rfloor m$$
Calculates \(c_1\) by compressing $u$ to \(d_u \) bits.
Calculates \(c_2\) by compressing $v$ to \(d_v \) bits.
Outputs ciphertext \(c = (c_1, c_2)\).
Kyber-PKE Decryption and Correctness
Alice:
Decompresses $u$ and $v$.
Computes:
$$v - s^Tu$$
- 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)$$
- 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:
Runs Kyber-PKE.KeyGen → \(((\rho, t), s)\).
Samples a random value \(z \in \{ 0, 1 \}^{256}\).
Sets:
$$dk = (s, ek, H(ek), z)$$
Kyber-KEM Encapsulation
Bob:
Obtains authentic $ek$.
Selects:
$$m \in \{0, 1\}^{256}$$
- Computes:
$$h = H(ek)$$
$$(K, R) = G(m, h)$$
with $H$ and $G$ being some hash functions.
- Uses Kyber-PKE.Enc to compute
$$c = PKE.Enc_{ek}(m; r)$$
- 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:
Use the Kyber-PKE to compute \(PKE.Dec_s(c)\) and call it the plaintext $m'$.
Compute:
$$(K', R') = G(m', H(ek))$$
Compute fallback \(\bar{K} = J(z, c)\) with J being a hash function.
Compute:
$$PKE.Enc_{ek}(m') = c'.$$
If \(c \neq c'\), then return \(\bar{K}\).
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
2. Lattice Math & LWE Tutorials
4. Implementation in the Wild
