Mental model
As you saw in M1, Shor’s algorithm breaks the problems RSA and ECC rely on (factoring, discrete logarithms). ML-KEM is a key encapsulation mechanism (KEM) that will replace them, resting on a different mathematical problem (Module Learning With Errors, Module-LWE). ML-KEM is defined in FIPS 203, which has FINAL2024-08-13 status, and it is the standardized form of CRYSTALS-Kyber, a finalist of the NIST competition. (You saw this intuition in more depth in the M2 lesson lattice-lwe-intuition; the “Module-LWE: what it rests on” section below is a short reminder of that definition in the context of ML-KEM’s own parameters.)
Three parameter sets, one standard
Much as RSA offers several key sizes, FIPS 203 defines three parameter sets for ML-KEM, each a different balance point between security and performance:
| Parameter set | Public key | Private key | Ciphertext | Category |
|---|---|---|---|---|
| ML-KEM-512 | 800 BSOURCED | 1632 BSOURCED | 768 BSOURCED | 1SOURCED |
| ML-KEM-768 | 1184 BSOURCED | 2400 BSOURCED | 1088 BSOURCED | 3SOURCED |
| ML-KEM-1024 | 1568 BSOURCED | 3168 BSOURCED | 1568 BSOURCED | 5SOURCED |
The shared secret is the same in all three parameter sets: 32 BSOURCED. The security categories (1, 3, 5) are a comparative scale, defined in NIST’s original PQC call, against a block cipher or hash function. FIPS 203’s own text does not define this scale as “a single number” (for example “128-bit security”) but as “the resources needed to break a particular block cipher in a realistic model of computation are at least this much”; it avoids claiming an exact number of bits.
NIST’s recommendation: ML-KEM-768
FIPS 203’s own text is clear: “NIST recommends using ML-KEM-768 as the default parameter set, as it provides a large security margin at a reasonable performance cost.” The same section also carries a warning: choosing the strongest parameter set (1024) has the advantage of “reducing the risk of a costly future transition”, but it may be unacceptably slow in some applications, or its key and ciphertext sizes may be unacceptably large. This is a warning, from the standard itself, that the “pick the strongest” reflex is not always the right decision. Passing this nuance to a bank architect (not a blind “strongest is best” decision but a balanced recommendation from FIPS 203’s own text) builds credibility.
Module-LWE: what it rests on
ML-KEM’s security rests on the hardness of the Module Learning With Errors (Module-LWE) problem. Intuitively: you have a set of linear equations (like the “two equations in two unknowns” from school, but in much higher dimensions), and normally solving such a system is easy. Module-LWE adds a small random “noise” (error) to each equation; that noise makes the equations unsolvable by classical methods, because telling which part is real signal and which is noise becomes practically impossible in a high-dimensional space. The problem can also be stated geometrically: it is equivalent to finding the lattice point closest to a given point in a high-dimensional lattice (a structure of regularly spaced points), and this has no efficient solution for classical or quantum computers (with the algorithms known so far). Module M2 covers this geometric intuition in more detail.
FIPS 203’s own text frames this security as “it is believed to be secure, even against adversaries who possess a quantum computer”, without claiming certainty. This is another example of the discipline you will see throughout this course: “claimed security and proven security are different”. The word “believed” is not an accident: there is no mathematical proof that Module-LWE cannot be broken (just as P≠NP has not been proven), only that years of intense cryptanalysis have not found a weakness. That is the same epistemic situation as RSA resting on the hardness of factoring; both offer security that is “heavily tested and still standing”, not “proven”.