Lattice-Based Cryptography
A lattice is an infinite, perfectly regular grid of points β but described by a basis that can make the same grid look either beautifully simple or hopelessly tangled. That gap between a good basis and a bad basis is where modern post-quantum cryptography lives: easy if you hold the good basis, apparently intractable if you only see the bad one.
The one-sentence idea. Publish a skewed, long-vector basis for a lattice; keep a short, nearly orthogonal basis secret. Anyone can scramble a message into the lattice, but only the holder of the good basis can reliably find the nearest lattice point and unscramble it β and no known algorithm, classical or quantum, closes that gap in high dimensions.
1 β What is a lattice?
Take two vectors that are not on the same line. Every integer combination of them is a lattice point:
| Lattice generated by a basis | |
|---|---|
| Fundamental parallelogram area | One lattice point per cell of this area, on average β the density of the lattice. |
The lattice itself is just the set of points. The basis is a choice of generating vectors β and, crucially, the same lattice has infinitely many bases. Some are short and nearly perpendicular. Others are long, nearly parallel, and hide the latticeβs simple structure. Everything below turns on that distinction.
2 β Skewing a basis: same area, worse vectors
Start with the perfect basis and shear the second vector sideways. The lattice points slide, the fundamental parallelogram leans β but its area never changes, because the determinant stays at 1. What degrades is the quality of the basis, measured by the orthogonality defect:
| Sheared basis | |
|---|---|
| Length of the sheared vector | |
| Orthogonality defect | A value of 1 means perfectly orthogonal. Larger means more skewed. The dot here is genuine multiplication of the two lengths. |
Figure 1. Drag the slider: the points shear sideways and the gold parallelogram leans, yet it always covers area 1 and the point density never changes. A skewed basis does not change the latticeβs density β it changes how hard the basis is to work with. At s = 0.85 the second vector is about 31% longer and the angle has closed from 90Β° to about 49.6Β°.
How to read this
- Good basis (small s): short, nearly perpendicular vectors. Rounding and nearest-point searches behave well.
- Bad basis (large s): longer, nearly parallel vectors. The same arithmetic becomes numerically treacherous β see Figure 4.
- Area is invariant: shearing is a volume-preserving change of description, not a change of lattice density.
3 β Same lattice, two completely different bases
Here is the cryptographic trapdoor in miniature. Both panels show exactly the same points β the integer lattice. The left basis is the obvious one. The right basis uses long vectors, yet generates precisely the same set, because its determinant is also 1:
| Good basis | |
|---|---|
| Bad basis | |
| Bad-basis lengths |
Good basis: short and orthogonal
Defect = 1.00. Each step moves one unit in one direction.
Bad basis: long and skewed
Defect β 7.07. Identical dots β only the arrows changed.
Figure 2. If someone hands you only the orange arrows, recovering the teal arrows β a process called basis reduction β is easy in 2D and brutally hard in high dimensions. That asymmetry is the trapdoor: the good basis is the private key, the bad basis is the public key.
4 β The shortest vector problem (SVP)
Every lattice with determinant 1 in 2D is guaranteed a surprisingly short non-zero vector β Minkowskiβs theorem promises one of length at most . Finding it, however, is another matter when your only basis is bad. In our example the shortest vector is (1, 0), of length 1. In the good basis it is simply the first basis vector. In the bad basis it is hidden as a difference:
| Shortest vector, bad-basis form | |
|---|---|
| Minkowski bound (2D, det 1) |
Figure 3. The teal arrow is the difference of the two long orange arrows. Nothing about the bad basis hints that this short combination exists β in 768 dimensions, searching all such combinations is hopeless, and the best known algorithms (sieving, enumeration, BKZ reduction) still cost time exponential in the dimension.
5 β The closest vector problem (CVP)
Given a point that is not on the lattice, find the nearest lattice point. The naive method β express the target in the basis, round each coefficient to the nearest integer (Babai rounding) β works beautifully with a good basis and fails with a bad one. Drag the blue target and watch both answers update.
Default target t = (2.4, 0.6). With the good basis, rounding gives (2, 1). With the bad basis, first invert:
| Bad-basis inverse | |
|---|---|
| Target in bad-basis coordinates | Rounding to (1, β1) reconstructs the lattice point (1, 0) β not the closest one. |
| Good-basis answer distance | |
| Bad-basis answer distance |
Figure 4. At the default target, bad-basis rounding lands nearly three times farther away than the true closest point (1.52 against 0.57). Drag the target into different cells: the good basis is always right or near-right, while the bad basis fails whenever the target sits in the long, thin part of its skewed cells. Decryption is exactly this step β the legitimate receiver rounds with the good basis; an attacker, stuck with the bad one, cannot. With the bases shown, the faint teal unit squares and orange skewed parallelograms are the two basesβ cells tiling the plane, and the highlighted cell around each answer is the set of targets that round to it: each method snaps the target to the centre of its own cell, which is how one target produces two different answers. At the origin the teal arrows are the good basis and the orange arrows the bad basis, each labelled b1 or b2 in its basis colour. Untick the checkbox for the cleaner picture without them.
6 β Learning with errors (LWE): CVP in disguise
Most deployed lattice schemes are not built directly on CVP but on LWE. A secret vector s is hidden by publishing near-exact dot products, each perturbed by a tiny error. Removing the error is a closest-vector search. A fully checkable toy, modulo 17, with secret s = (3, 5):
| Sample 1: exact value | |
|---|---|
| Sample 1: published, error +1 | |
| Sample 2: exact value | |
| Sample 2: published, error β1 |
Here are the two samples drawn out. In each panel the top line runs from the raw dot product down to its remainder β every full wrap of 17 is subtracted at once β and the bottom line sits inside a single mod-17 range, where one small error step moves the clean remainder to the published value:
Sample 1: aβ = (4, 7), published bβ = 14
47 wraps past 17 and 34, landing on the remainder 13, the clean lattice value. One +1 error step publishes 14 instead.
Sample 2: aβ = (2, 9), published bβ = 16
51 is exactly three wraps, so the remainder is 0. The β1 error step walks off the left end of the range and wraps to 16: that is β1 mod 17.
Without the errors, two samples would be two linear equations and s would fall to Gaussian elimination instantly. The Β±1 errors destroy linearity: the only known routes recover s by solving a closest-vector problem in a lattice built from the samples. Geometrically β and interactively, since you can drag the blue received point (the tip of the error arrow) in Figure 5:
Figure 5. Each LWE sample is a lattice point nudged by a small error. Decoding means finding which lattice point the received point came from β CVP again. The gold cell is the set of received points that still decode back to (3, 2): the unit square centred on it. Decoding succeeds exactly while the error stays inside that cell β each component strictly inside half a step, |e_x| < 0.5 and |e_y| < 0.5. Drag the tip past an edge and the received point snaps to the neighbouring lattice point instead: the original is lost. The error must be small enough for the good-basis holder to correct, yet large enough that the attacker cannot simply round it away with the public bad basis.
7 β From 2D to 3D, and then imagine 768
In 3D a basis has three vectors and the lattice fills space. Rotate the view: the points are the integer combinations of three unit vectors, with two example combination vectors drawn inside: v = (2, 1, 1) in teal and w = (1, 2, 0) in gold. Notice how even in 3D, nearest-point intuition already gets slippery as points occlude each other.
Figure 6. Now extrapolate. Real schemes do not use dimension 3, or 30. ML-KEM (Kyber-768) works in dimension 768, a module lattice of rank 3 over a ring of dimension 256. There is no picture of that lattice and no neighbourhood small enough to search: the number of nearby lattice points explodes combinatorially, and every known attack scales exponentially in the dimension. The 2D failures you caused by dragging in Figure 4 become, in 768 dimensions, an absolute wall.
Why dimension is the security dial. In 2D, Gauss reduction finds the good basis instantly. In a few hundred dimensions, the best reduction algorithms (BKZ with large block sizes, sieving) need astronomically many operations β and unlike factoring or discrete logarithms, no quantum algorithm is known that changes this picture. Shorβs algorithm broke RSAβs underlying problem; no analogue is known for SVP, CVP, or LWE.
8 β The essential problems and the real schemes
| Problem | Task | Role in cryptography |
|---|---|---|
| SVP | Find the shortest non-zero lattice vector | Hardness benchmark; attacking a scheme usually reduces to approximate SVP |
| CVP | Find the lattice point nearest a given target | Decryption: the receiver performs this with the good basis |
| LWE | Recover a secret from dot products perturbed by small errors | Basis of ML-KEM and ML-DSA; provably as hard as worst-case lattice problems |
| SIS | Find a short integer combination that vanishes modulo q | Hash functions and signature constructions |
| Standard | Also known as | Purpose | Working dimension |
|---|---|---|---|
| ML-KEM (FIPS 203) | Kyber | Key encapsulation: agreeing on a shared secret | 512, 768, or 1024 (Kyber-768: rank 3, ring dimension 256) |
| ML-DSA (FIPS 204) | Dilithium | Digital signatures | Module lattices over a 256-dimensional ring |
The whole story in four lines
- A lattice is a regular grid; a basis is a way of describing it, and descriptions vary from excellent to terrible.
- Rounding and nearest-point search are easy with a good basis and fail with a bad one β you measured the failure yourself in Figure 4.
- LWE turns that geometric gap into algebra: exact equations plus small errors, decodable only via a closest-vector search.
- At dimensions of 512 to 1024, no known classical or quantum algorithm bridges the gap in feasible time β which is why these schemes are the post-quantum standards.
