A Teaching Model of Noisy Public Equations

The secret hidden
by a little noise

A square linear system has a unique solution when its matrix is invertible. This demo samples invertible matrices modulo 97. With zero error, elimination recovers the secret. With nonzero error, solving the exact equations generally recovers a different vector; a tiny instance remains easy to attack by enumerating the possible secrets.

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.

error bound

—

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.

§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.

Noise prevents exact elimination from being a general secret-recovery method. Security requires suitable dimensions, distributions and parameters: small error does not automatically make every instance hard. LWE and Module-LWE specify such sampling problems, with Module-LWE using structured modules over polynomial rings.

§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.

send bit error bound

—

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 the sent ideal. An error strictly below 24 guarantees correct decoding here; at 24 the outcome depends on the bit, direction and tie rule. Larger errors decode incorrectly. Raise the error and watch the bar climb.

§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. The ternary secret here has only 81 possibilities; it is here to be readable, not hard.
The randomnessuniform, not GaussianML-KEM draws relevant small values from centered binomial distributions; other schemes use different distributions, 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 an LWE-inspired one-bit encryption model, not a standard-compatible implementation. 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

ML-KEM uses this broad structured noisy-equation pattern at much larger parameters, with additional operations omitted here. No efficient classical or quantum attack is known for its intended security targets. That expectation is based on cryptanalysis of the specified problems, not a proof that merely adding noise eliminates every exploitable quantum structure.

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.