Lattice-Based Cryptography

Table of Contents

Post-quantum cryptography β€” the geometry underneath

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 basisL={ab1+cb2:a,cβˆˆβ„€}
Fundamental parallelogram areaarea=|det(B)|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 basisb1=(1,0)b2=(s,1)
Length of the sheared vector|b2|=s2+1
Orthogonality defectΞ΄=|b1|Β·|b2||det(B)|A value of 1 means perfectly orthogonal. Larger means more skewed. The dot here is genuine multiplication of the two lengths.
b₁ = (1, 0) bβ‚‚ = (s, 1) lattice points

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Β°.

Figure 1: Shear s = 0.00, a nearly orthogonal (good) basis

1.00Length of bβ‚‚
1.00Orthogonality defect Ξ΄
90.0Β°Angle between b₁ and bβ‚‚
1.00Parallelogram area (det)

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 basisb1=(1,0)b2=(0,1)det=1Β·1βˆ’0Β·0=1
Bad basisb1=(3,1)b2=(2,1)det=3Β·1βˆ’1Β·2=1
Bad-basis lengths|b1|=10β‰ˆ3.16|b2|=5β‰ˆ2.24Ξ΄=50β‰ˆ7.07

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 2β‰ˆ1.41. 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(1,0)=(3,1)βˆ’(2,1)=b1βˆ’b2
Minkowski bound (2D, det 1)Ξ»1≀2β‰ˆ1.41
bad basis vectors shortest vector (1, 0)

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 inverseBβˆ’1=[1βˆ’2βˆ’13]
Target in bad-basis coordinatesBβˆ’1t=(1.2,βˆ’0.6)Rounding to (1, βˆ’1) reconstructs the lattice point (1, 0) β€” not the closest one.
Good-basis answer distance0.32β‰ˆ0.57
Bad-basis answer distance2.32β‰ˆ1.52
target t (drag me) good-basis rounding bad-basis rounding good basis: b1 = (1, 0), b2 = (0, 1) bad basis: b1 = (3, 1), b2 = (2, 1)
(2.40, 0.60)Target t
(2, 1), d = 0.57Good basis: point, distance
(1, 0), d = 1.52Bad basis: point, distance
(2, 1), d = 0.57True closest point

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 value4Β·3+7Β·5=47≑13(mod17)
Sample 1: published, error +1b1=13+1=14
Sample 2: exact value2Β·3+9Β·5=51≑0(mod17)
Sample 2: published, error βˆ’1b2=0βˆ’1≑16(mod17)

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

a1Β·s=4Β·3+7Β·5=12+35=4747βˆ’2Β·17=13b1=13+1=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

a2Β·s=2Β·3+9Β·5=6+45=5151βˆ’3Β·17=0b2=0βˆ’1≑16(mod17)

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:

exact lattice point (3, 2) error e (drag its tip) received point (lattice point + error) cell of points that decode back to (3, 2) point it snaps to when lost
(+0.20, +0.15)Error e = (e_x, e_y)
0.25Length |e|
(3, 2)Decodes to (nearest point)
RecoveredGood-basis decoding

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.

Figure 5: Error length = 0.25, decoding recovers (3, 2)

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.

v = (2, 1, 1) w = (1, 2, 0) lattice points

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.

Figure 6: 3D lattice, azimuth = 35Β°

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

ProblemTaskRole in cryptography
SVPFind the shortest non-zero lattice vectorHardness benchmark; attacking a scheme usually reduces to approximate SVP
CVPFind the lattice point nearest a given targetDecryption: the receiver performs this with the good basis
LWERecover a secret from dot products perturbed by small errorsBasis of ML-KEM and ML-DSA; provably as hard as worst-case lattice problems
SISFind a short integer combination that vanishes modulo qHash functions and signature constructions
StandardAlso known asPurposeWorking dimension
ML-KEM (FIPS 203)KyberKey encapsulation: agreeing on a shared secret512, 768, or 1024 (Kyber-768: rank 3, ring dimension 256)
ML-DSA (FIPS 204)DilithiumDigital signaturesModule 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.
All numeric examples on this page are small enough to check by hand: determinants, lengths, rounding results, and the mod-17 arithmetic are stated alongside each figure.