Lattices and Their Hard Problems: SVP, CVP, and the Geometry of Security

The cryptography that will outlast quantum computers does not rest on factoring or discrete logarithms; it rests on a shape. A lattice is nothing more exotic than a regular grid of points extending through a high-dimensional space, and the security of the standardized post-quantum schemes reduces to a single, sturdy intuition about such grids: it is easy to navigate a lattice when you hold a description made of short, roughly perpendicular vectors, and it becomes intractable when you hold a description made of long, skewed ones — even though both describe the identical set of points. This article assembles the geometric foundation carefully, defining the objects and the hard problems from scratch, so that the later machinery of Learning With Errors and the module lattices behind the standards rests on solid ground.

What a lattice is

A lattice is a discrete, regularly repeating set of points in n-dimensional real space. Concretely, fix n linearly independent vectors — call them a basis — and take every point reachable by adding integer multiples of those basis vectors. The resulting infinite set of points, closed under addition and negation, is the lattice they generate. The integer-combination requirement is what makes it discrete: unlike the continuous span of the same vectors, which fills a subspace, the lattice is a grid with gaps between its points.

Two quantities describe a lattice independently of how it is presented. The determinant, the absolute value of the determinant of any basis matrix, measures the volume of the repeating cell and is the same for every basis of the same lattice — it is an invariant. The first minimum, written lambda-one, is the length of the shortest nonzero lattice vector; it captures how tightly packed the lattice is. Minkowski's theorem bounds the first minimum from above in terms of the determinant and the dimension, guaranteeing that a reasonably short vector exists even when finding it is hard.

The crucial structural fact is that a single lattice has infinitely many bases. Any basis can be transformed into another by an integer matrix with determinant plus or minus one — a unimodular transformation — and the new vectors still generate exactly the same points. Some of these bases are short and nearly orthogonal; others are long and highly skewed. They describe the same geometry but expose it to wildly different degrees.

Good bases, bad bases, and the trapdoor

The entire cryptographic use of lattices flows from the difference between a good and a bad basis for the same lattice. A good basis consists of short, nearly orthogonal vectors. With it, locating the lattice point nearest to an arbitrary target is easy: express the target in the basis and round each coordinate to the nearest integer — Babai's rounding — and because the vectors are short and orthogonal the rounding error stays small and the true nearest point is found. Navigation is trivial when the map is well-drawn.

A bad basis for the identical lattice consists of long, skewed vectors. Rounding in that basis produces large errors that overshoot the true nearest point, so the easy algorithm fails, and finding the nearest point becomes intractable in high dimension. The lattice is unchanged; only the description has degraded, and with it the ability to reason about the geometry. This asymmetry is the trapdoor: publish the bad basis as a public key so that anyone can pose problems on the lattice, and keep the good basis as a secret key so that only its holder can solve them.

This is the conceptual core that Learning With Errors and the standardized schemes make precise and quantitative. Encryption hides a message as a point deliberately placed near the lattice; decryption is the closest-vector computation that only the good basis makes feasible. Everything else is the machinery of choosing lattices for which a bad basis is genuinely hard to improve.

The canonical hard problems

Lattice cryptography rests on a small family of computational problems, all variants of finding short or near vectors. The shortest vector problem asks for a nonzero lattice vector of minimum length — a vector achieving lambda-one. The closest vector problem asks, given an arbitrary target point not on the lattice, for the lattice point nearest to it. These are the two anchors; the closest vector problem is known to be NP-hard, and the shortest vector problem is NP-hard under randomized reductions.

Cryptography uses relaxed and decisional forms of these. The approximate shortest vector problem asks for a vector within a factor gamma of the true minimum length rather than exactly minimal, because approximate hardness is what a security proof needs. The decisional gap variant, GapSVP, asks only to distinguish lattices whose shortest vector is short from those whose shortest vector is long, by a gamma factor — a decision, not a search. A further variant, the shortest independent vectors problem, asks for a full set of short independent vectors and underlies the worst-case reductions.

The reason to name all of them is that the security of the standards is proved by reduction to these problems: an efficient attack on the scheme would yield an efficient algorithm for one of them, which is believed not to exist. The problems are the fixed points; the schemes are constructions that inherit their hardness.

The approximation regime cryptography lives in

Exactness matters here, because the hardness of these problems depends sharply on the approximation factor gamma. Finding an exactly shortest vector, gamma equal to one, is NP-hard. At the opposite extreme, the classic lattice-reduction algorithm of Lenstra, Lenstra and Lovasz finds a vector within a factor exponential in the dimension in polynomial time — so for very large gamma the problem is easy. Cryptography lives in the middle: it relies on the hardness of approximating within a factor polynomial in the dimension, a regime for which no efficient algorithm, classical or quantum, is known.

This middle regime is the load-bearing assumption. The security proofs of the standardized schemes reduce breaking the scheme to solving GapSVP or the shortest independent vectors problem to within a polynomial factor, in the worst case over all lattices of a given dimension. The polynomial-factor regime is believed hard precisely because decades of algorithmic effort — lattice reduction, sieving, enumeration — have not produced a polynomial-time algorithm for it, and quantum computers have offered no exponential improvement, in sharp contrast to their effect on factoring.

It is worth stating the honesty of the situation: this is a hardness assumption, not a theorem that P differs from NP. What makes it a strong assumption is the combination of worst-case guarantees, the long unbroken history of attempts, and the absence of any quantum shortcut of the kind that dooms number-theoretic cryptography.

Why worst-case hardness is the security anchor

A distinctive strength of lattice cryptography, established by Regev and by the ideal- and module-lattice reductions that followed, is a worst-case to average-case connection. Ordinary cryptography assumes that a randomly chosen instance of a hard problem — a random modulus to factor — is hard, which is an average-case assumption. Lattice schemes can be based on the assumption that the underlying problem is hard in the worst case over all lattices of the dimension, which is a stronger and more comfortable foundation: breaking a random instance of the scheme would imply an algorithm that solves every lattice instance, including the hardest.

This matters because it removes a common worry — that the specific random instances a scheme generates might happen to be easy even if the problem is hard in general. The worst-case reduction rules that out: there are no weak instances to stumble into, because solving the average case would solve the worst case. The security of the standards therefore rests not on the hope that random lattices are hard but on the assumption that the hardest lattice of each dimension is hard, transported to the average case by proof.

The geometry, then, is doing real cryptographic work. A lattice is a grid; its determinant and first minimum describe its packing; its many bases range from revealing to concealing; the hard problems ask for short or near vectors within a polynomial factor; and the worst-case reduction anchors the whole edifice. The remaining articles turn this geometry into the concrete distributions and parameters of the deployed schemes.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

lattice_scheme:
  base_problem: GapSVP        # or SIVP, via Module-LWE
  approximation_regime: polynomial_factor
  reduction: worst_case_to_average_case
  dimension_parameter: n      # record concrete value
  attacks_considered: [lattice_reduction, sieving, dual]
  quantum_speedup_known: none_exponential
audit:
  primary_source: cited

Glossary

Lattice

The set of all integer linear combinations of a set of linearly independent basis vectors; a discrete additive subgroup of real space.

Basis / unimodular transform

A generating set for a lattice; two bases of the same lattice differ by an integer matrix of determinant plus or minus one.

Determinant and first minimum

The cell volume (basis-independent) and the length lambda-one of the shortest nonzero lattice vector; Minkowski bounds the latter by the former.

Shortest / closest vector problem

SVP asks for a minimum-length nonzero lattice vector; CVP asks for the lattice point nearest a given target.

Approximation factor (gamma)

The multiplicative slack in an approximate problem; hardness rises as gamma shrinks toward one and falls as it grows.

Worst-case-to-average-case reduction

A proof that solving random instances of a scheme would solve every lattice of that dimension, removing the risk of weak random instances.

References

1. Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (JACM, 2009)
2. Lyubashevsky, Peikert & Regev, On Ideal Lattices and Learning with Errors over Rings (EUROCRYPT, 2010)
3. Langlois & Stehle, Worst-Case to Average-Case Reductions for Module Lattices (Designs, Codes and Cryptography, 2015)
4. Albrecht, Player & Scott, On the Concrete Hardness of Learning with Errors (IACR ePrint 2015/046)
5. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)