The KEM Contract

01.Three algorithms

A key encapsulation mechanism is a triple:

$\textsf{KeyGen}()$ outputs a public and secret key pair $(pk, sk)$.

$\textsf{Encaps}(pk)$ outputs a ciphertext $c$ together with a shared key $K$ of 256 bits.

$\textsf{Decaps}(sk, c)$ outputs a key $K$.

Correctness: for honestly generated keys and an honestly produced $(c, K)$, decapsulation returns the same $K$ that encapsulation produced.

Note what is absent. There is no message input anywhere. $\textsf{Encaps}$ takes only a public key, and the key it produces is an output rather than an argument. That is the distinction from ordinary encryption described in the previous note.

02.Two kinds of attacker

Security is where the design decisions actually come from, and the whole shape of ML-KEM follows from one distinction.

A passive attacker reads everything on the wire and cannot change anything. They see ciphertexts going past and try to learn something about the keys. Security against this is called IND-CPA, where CPA stands for chosen-plaintext attack, and IND for indistinguishability, meaning the attacker cannot even tell a real ciphertext from random bytes.

An active attacker can additionally send ciphertexts of their own choosing to Bob and observe what happens. They can send a malformed ciphertext and watch for an error message, a timing difference, a retry, or any change in behaviour. Security against this is called IND-CCA, for chosen-ciphertext attack.

Real networks are the second kind. Anybody positioned to read packets between two machines is generally also positioned to modify or inject them, and a server that accepts connections from the public Internet will accept whatever an attacker sends it. Any deployed KEM must survive an active attacker or it is worthless.

03.Why the distinction bites

It is worth seeing concretely why a passively secure scheme can fall apart against an active one, because the abstraction hides how sharp the difference is.

Suppose Bob's server decrypts a ciphertext and returns an error whenever the result fails some internal check. An attacker takes a legitimate ciphertext, modifies one coefficient slightly, and sends it. Sometimes the modification is small enough that decryption still succeeds, sometimes it pushes a coefficient over a threshold and the server errors.

Which of those happened depends on how close that coefficient already was to the threshold, which depends on the secret key. So each query leaks a bit of information about $sk$. Repeat a few thousand times, and the key can be reconstructed.

Nothing in that attack breaks the underlying mathematics. Module-LWE is untouched. The attack works entirely through the server's reaction, which is a channel the passive model does not model at all.

Attacks of exactly this form have broken real deployed systems repeatedly, including several padding-oracle attacks against RSA and TLS. This is a well-trodden failure mode rather than a theoretical concern.

04.The two-layer construction

Building an IND-CCA scheme directly from lattice assumptions is difficult. ML-KEM does not try. It uses a two-layer structure that is now standard across essentially every post-quantum KEM.

The inner layer is a public-key encryption scheme built on Module-LWE. It is IND-CPA secure, meaning it withstands eavesdroppers. All the lattice mathematics is here.

The outer layer is a generic transform, due to Fujisaki and Okamoto, that upgrades any suitable IND-CPA scheme to IND-CCA. It contains no lattice mathematics whatsoever and would work over a completely different inner scheme.

The separation is worth appreciating as engineering rather than accepting as convention. The hard, novel, lattice-specific reasoning is confined to a layer that only has to defeat a passive attacker, which is a far easier target. The defence against active attackers is a generic piece of plumbing that has been analysed independently and reused across many schemes. Neither layer has to be clever about the other's problem.

Notes 4 through 7 build the inner layer. Note 8 wraps it, and explains the specific trick, called implicit rejection, that closes the reaction channel described above.