← Hall of Foundations Exhibit 157 · t = As + e
What ML-KEM & ML-DSA Actually Hold

The secret hidden
by a little noise

Schoolroom algebra says a system of linear equations with as many equations as unknowns has exactly one solution, and a mechanical procedure finds it. That is completely true. Learning With Errors breaks it anyway — by perturbing every equation just slightly, so the procedure still runs, still returns an answer, and the answer is worthless.

A public key you can read. The essential public relation behind ML-KEM is on this page: a public matrix, and a noisy product of that matrix with a short secret vector. A real key adds seeds, encodings and compression on top — §4 lists what this leaves out — but the relation is the part that carries the security. Set the error to zero and the secret falls out in one click, which is the fastest way to see what the error is for.
§1

A system anyone can solve

Below is a public matrix A and a public vector t, both with entries modulo q = 97. Hidden behind them is a short secret vector s — every entry is −1, 0, or 1. The relationship is the plainest one in mathematics:

t = A·s + e  (mod 97)

Set the error to zero and that e vanishes, leaving t = A·s. Press Solve and Gaussian elimination — the same procedure you learned for three equations in three unknowns — recovers s instantly and exactly, every time. There is no security here at all.

—
The error bound is the largest value any entry of e may take, plus or minus. At 0 the system is exact and elimination wins. Nudge it to 1 — a perturbation of at most one, in a world 97 wide — and the same elimination returns a vector with nothing in common with the real secret.
Keyboard alternative: set the error bound with the slider, then activate Solve. Results are announced in the readout.
§2

Why so small a change ruins it

Elimination works by scaling rows and subtracting them from one another. Modulo a prime, "scaling" means multiplying by numbers like 43 or 88 — there is no notion of a small multiplier to keep things tidy. So a single unit of error, multiplied by 43 and added to another row's error, multiplied again at the next step, is smeared across the whole computation within a few rows.

The algorithm never fails, never warns, and never notices. It returns a confident answer that happens to be noise.

That is the asymmetry the whole construction rests on. The error is far too small to interfere with anyone who knows s, and far too destructive for anyone applying exact linear algebra without it. Recovering s from (A, t) is the LWE problem; doing it with polynomials instead of plain numbers, as the standards do, is Module-LWE, and it lives in the ring next door.

§3

The cancellation that lets the owner in

A hard problem alone is not cryptography — the legitimate recipient has to get through. Encryption picks fresh small randomness r and sends two things: a vector u = Aᵀr + e₁, and a number v = t·r + e₂ plus the message bit multiplied by ⌊q/2⌋ — a value large enough to spot from across the ring.

Decryption computes v − s·u. Expand both sides and a large term appears twice, with opposite signs:

v − s·u = sᵀAᵀr + e·r + e₂ − s·e₁ + m·⌊q/2⌋  →  m·⌊q/2⌋ + small

The bulk cancels. What survives is the message bit, sitting on top of a pile of error terms that were all small to begin with. Round to whichever of 0 or ⌊q/2⌋ is nearer, and the bit falls out. Nothing here rounds with a private basis — the secret's job is to make one big term disappear.

—
The bar shows how far the decrypted value landed from the ideal m·⌊q/2⌋ for the bit that was actually sent. The vermilion line is the budget, ⌊q/4⌋ = 24; the track runs to 48, the furthest a value can sit from either ideal. Cross the line and the rounding tips to the wrong bit. Raise the error and watch the bar climb.
Keyboard alternative: choose a bit and an error bound, then activate Encrypt and decrypt. The residual noise and recovered bit are announced.
§4

Honest limits of this model

Three things here are toys, and it is worth naming them.

  • The size4 × 4, q = 97ML-KEM works over a 256-coefficient polynomial ring with q = 3329, arranged in modules of rank 2 to 4. A 4×4 system mod 97 is brute-forceable in microseconds; it is here to be readable, not hard.
  • The randomnessuniform, not GaussianReal schemes draw errors from a centered binomial distribution, and the security proofs depend on that shape. This exhibit picks uniformly in a range, which makes the slider legible but is not what gets deployed.
  • The schemeone bit, no KEMThis is Regev-style encryption of a single bit. ML-KEM is a key-encapsulation mechanism with compression, a Fujisaki–Okamoto transform for chosen-ciphertext security, and rejection steps this page has no equivalent of.

What is faithful is the shape: the public key really is a matrix plus a noisy product, the secret really is a short vector, decryption really does work by cancelling a shared term, and the noise budget really is the thing parameter choices are fighting over.

Where this touches your keys

The bet the post-quantum standards make

Whenever a browser negotiates ML-KEM, this structure is running at full size. The reason it is expected to survive a quantum computer is that Shor's algorithm attacks periodicity — the hidden repeating structure inside factoring and the discrete log, both of which live in the cyclic groups of §149. Noisy linear algebra over a module has no such period to find. That is the whole bet, and it is a different bet from the one RSA and Diffie–Hellman made.

Three views of one problem. §147 is the geometry — why the secret stays hidden. §152 is the decoding — why its owner still gets in. §157 is the algebra — what the keys are actually made of. Next: Polynomial Rings, where these plain vectors become polynomials. Tested logic in lwe-math.js.