← Hall of Foundations Exhibit 152 · CVP → LWE
The Problem ML-KEM (Kyber) Actually Leans On

Finding the
nearest corner

Its sibling exhibit asked for the shortest vector in a lattice. This one asks something subtler: given a target point floating off the grid, which lattice corner is closest? Answer it and you can decrypt. Fail, and you're staring at noise. This is the ground Kyber stands on.

The same lattice, two fortunes. With a "good" basis — short, near-perpendicular vectors — the closest corner falls out of a single rounding step. With a "bad" basis for that same lattice, the rounding lands on the wrong corner most of the time. That gap is the shape of a lattice trapdoor, and it is what a noise term is defending. Read the two bases as a model of that asymmetry: §4 below shows the rather different form ML-KEM's own key takes.
§1

A point that isn't on the grid

Drag the target anywhere. The Closest Vector Problem asks for the lattice point nearest to it. In two dimensions your eye finds it instantly — but your eye is using the grid's true shape, which the attacker doesn't get to see.

—
The teal ring is the true closest corner. The vermilion square is where Babai rounding with the current basis lands. With a good basis they coincide; with a bad one they part ways.
Keyboard alternative: set the target coordinates and choose a basis, then round.
§2

Rounding in the basis you're handed

The natural algorithm — Babai's rounding — rewrites the target in terms of the two basis vectors, then rounds each coordinate to the nearest whole number. It's fast and exact when the vectors are short and near-perpendicular. When they're long and skewed, the rounding boxes are stretched slivers, and the nearest lattice coordinates point at the wrong corner.

t = a·b₁ + b·b₂  →  round(a), round(b)  →  nearest corner?
  • Good basisthe trapdoorShort, near-perpendicular vectors. Rounding lands on the true nearest corner every time.
  • Bad basiswhat an attacker getsLong, skewed vectors for the same lattice. Rounding misfires on most targets — about four in five.
§3

Add noise, and you have Learning With Errors

Here is the geometric model behind noisy lattice encryption. Take a genuine lattice point, nudge it by a small random error, and publish the result — that's a ciphertext. Decryption is a Closest Vector Problem: round back to the nearest corner to recover the point. It works only while the noise stays inside the cell around that corner. Push the noise slider and watch even the good basis start to fail as the error grows past what its cell can absorb.

—
The ink dot is the true point (the message). The vermilion dot is the published ciphertext = point + noise. Decryption succeeds when rounding returns the ink dot — a teal ring. As σ grows, the good basis holds far longer than the bad one.
Security is the noise. Too little and it's plain CVP; enough, in high dimensions, and only the good-basis holder can round back home.
§4

What ML-KEM actually holds

The two-basis picture above is the classical way to build a lattice trapdoor, and it is how schemes in the GGH and NTRU lineage work. It is not how the deployed standards are keyed, and the difference is worth stating plainly. ML-KEM (Kyber) and ML-DSA (Dilithium) publish a matrix A together with a noisy product of that matrix and a short secret vector:

public: (A, t)  where  t = A·s + e  ·  secret: the short vector s

There is no secret good basis anywhere in that key. §157 is that equation, live — solve it with the noise off, then switch the noise on and watch the same algebra collapse. Recovering s from (A, t) is the Module-LWE problem, which lives in the polynomial ring next door. Decryption does not round with a private basis either — it uses s to cancel the large shared term out of the ciphertext, leaving the message plus a little noise, and then rounds that away.

The secret is a short vector, not a short basis. Same geometric family, different key structure.

So why keep this exhibit? Because the geometry survives the change of key format. LWE is a bounded-distance decoding problem: the ciphertext is a point sitting near a lattice point, and everything you just watched — why a noise budget exists, why exceeding it breaks decryption, why a skewed view of a lattice is useless — is what the noise is defending. The best known attacks on ML-KEM run lattice reduction and then solve exactly this problem. The picture is right; only the key layout differs.

Where this touches your keys

Why the owner can still get in

Where the SVP exhibit showed why the secret stays hidden, this one shows why its holder can still decrypt — and why the noise budget is the whole game. Set the error too small and an attacker can decode the ciphertext themselves; too large and the legitimate recipient rounds to the wrong answer. Every lattice standard surveyed in Modern Cryptography is, in part, a careful choice of that margin.

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. Also related: Reduction & Proof, for what "reduces to this problem" claims.