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

An attacker given a basis has a description of the entire lattice. The difficulty of finding a closest point in suitable high-dimensional instances is computational, not that the grid's geometry was withheld.

—

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.

§2

Rounding in the basis you're handed

This demo uses coordinate rounding: express the target in the supplied basis, then round each coefficient. It is exact for the orthogonal good basis shown here. A merely short or nearly perpendicular basis does not guarantee exact rounding for every target. Skewed bases can make this simple algorithm fail.

t = a·b₁ + b·b₂ → round(a), round(b) → nearest corner?

Good basisthe trapdoorOrthogonal vectors in this preset. Coordinate rounding gives a nearest lattice point.
Bad basiswhat an attacker getsLong, skewed vectors for the same lattice. Rounding misfires on most targets — for many targets.

§3

A geometric model of noisy decoding

This is a geometric decoding model: add a random displacement of the displayed magnitude to a lattice point, then try to recover that original point. Decoding succeeds when the perturbation stays in that point's nearest-neighbor cell. This is not itself the LWE sampling distribution or a deployed encryption scheme.

noise σ basis

—

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

These keys contain short secret vectors, not a generic secret good basis. The public equations and their sampling rules lead to Module-LWE-related assumptions; ML-DSA also rounds the public product and uses additional assumptions. In ML-KEM's underlying encryption, the secret cancels a shared term before decoding. ML-DSA is a signature scheme and does not decrypt messages.

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

The connection is geometric intuition: lattice attacks can turn noisy equations into decoding or short-vector problems. Concrete attacks include primal, dual and hybrid approaches; it is inaccurate to say they all solve exactly this two-dimensional closest-point task. See the LWE exhibit for the public equations and message-cancellation model.

Where this touches your keys

Why the owner can still get in

This exhibit shows how decoding can recover a point from a bounded perturbation. Real encryption balances correctness and resistance to attacks using a complete parameter set. Signatures have different correctness conditions; a decryption noise budget is not a universal description of lattice cryptography.