Lattice Problems

The Shortest Vector Problem

A lattice was built as a geometric object: a discrete additive subgroup of \(\mathbb{R}^n\), the set of all integer combinations of a basis. From that geometry the previous pages extracted a single number that measures how tightly the lattice packs space near the origin — the length of its shortest nonzero vector, the first minimum \(\lambda_1(\mathcal{L})\). Everything on that page was about the existence of a short vector. Minkowski's convex body theorem guaranteed one without ever producing it, delivering the bound \[ \lambda_1(\mathcal{L}) \leq \sqrt{n}\,(\det \mathcal{L})^{1/n} \] from a volume argument that never inspects a single lattice point. This page asks the question that existence leaves open. A vector of that length is promised to be there; how hard is it to find?

The gap between the two questions is the entire subject. Existence is settled by geometry in one line; construction is, as far as anyone knows, intractable. Naming the construction problem precisely is the first step.

Two aspects of this definition repay a moment's attention, because both separate SVP from problems that look superficially similar and are in fact easy. The first is that the input is a basis, not the lattice as a set. The lattice is infinite; one never receives it directly. One receives a finite list of vectors whose integer combinations generate it, and the same lattice admits infinitely many such lists, related by the unimodular changes of basis catalogued earlier. Some bases are nearly orthogonal and reveal the short vectors at a glance; others are long and skewed and hide them completely. The difficulty of SVP is precisely the difficulty of recovering geometric information — the shortest vector — that a badly chosen basis obscures. A cryptographic construction will later exploit exactly this: it publishes a bad basis and keeps a good one secret.

The second aspect is that the length is measured in the Euclidean norm, and this is a genuine choice rather than a formality. The same problem posed in the \(\ell_\infty\) norm — where a vector's length is its largest coordinate in absolute value — behaves differently, and the difference will surface when we come to hardness. Unless stated otherwise, \(\|\cdot\|\) means the Euclidean length throughout, matching the norm in which \(\lambda_1\) was defined.

Why should finding \(\mathbf{v}\) be hard? The lattice is discrete, so a shortest vector exists and is one of finitely many candidates below any fixed length. One might hope to simply enumerate them. The obstruction is dimension. The number of lattice points inside a ball of fixed radius grows exponentially with \(n\), and the shortest vector can hide among integer combinations whose coefficients are individually large even when the vector they produce is small — a long, skewed basis arranges precisely this cancellation. Searching the coefficients directly is exponential in \(n\), and no method is known that avoids paying a cost of that order in the worst case. What replaces enumeration in practice is basis reduction, which improves a bad basis toward an orthogonal one; we return to its power and its limits at the end of the page.

In cryptographic settings one rarely needs the exact shortest vector. It is enough to find a vector that is short to within a factor — and, on the other side, hardness is more naturally established for the approximate problem than the exact one. Both considerations point to relaxing the definition by a factor \(\gamma \geq 1\).

The approximation factor \(\gamma\) is written as a function of the dimension deliberately. The whole story of lattice hardness is a story about how this factor scales with \(n\): the problem is NP-hard for factors close to \(1\), lands in a benign complexity class for factors around \(\sqrt{n}\), and becomes solvable in polynomial time only once \(\gamma\) is allowed to grow exponentially. A single family of problems, indexed by one growing parameter, stretches from intractable to easy. Locating the useful cryptographic regime within that stretch is the task of the approximation hierarchy developed later on this page.

Before that, a word on the honest state of the exact problem's hardness, because it comes with a subtlety that the definition's insistence on the Euclidean norm anticipated. That the exact shortest vector problem is hard is not a folk belief but a theorem — with a caveat about the norm. In the \(\ell_\infty\) norm, exact SVP is NP-hard, and the proof follows the same combinatorial route that settles the nearest-vector problem, which the next section takes up. In the Euclidean norm the question resisted for far longer; establishing NP-hardness there required substantially more machinery and a reduction that succeeds only with high probability rather than with certainty. The upshot is that exact SVP is hard, the Euclidean case genuinely harder to prove hard than the \(\ell_\infty\) case, and — a point the hierarchy will make precise — the hardness that actually supports cryptography is not this worst-case exact hardness at all, but the hardness of approximating to within a factor that grows with the dimension.

Distances to a Lattice

The shortest vector problem asks about the lattice in isolation: how close to the origin does a nonzero lattice point come? A second, equally natural question introduces an outside point. Given a target \(\mathbf{t} \in \mathbb{R}^n\) that is typically not itself in the lattice, which lattice point lies nearest to it? This is the closest vector problem, and it is in a precise sense the more fundamental of the two: much of the hardness of SVP is inherited from it, as the next section shows by reducing one to the other.

We state it, but — unlike SVP — we do not enshrine it as a named object the rest of the track will link to. The reason is structural and worth making explicit, since it recurs. The cryptographic constructions this track builds toward rest on the shortest-vector side and on two close relatives defined below; the closest vector problem in its full generality serves here as the source of hardness and the parent of those relatives, not as a load-bearing definition in its own right. It is the conceptual hub, described precisely and then set to one side.

Given a basis \(\mathbf{B}\) of \(\mathcal{L} \subseteq \mathbb{R}^n\) and a target \(\mathbf{t} \in \mathbb{R}^n\), the closest vector problem (CVP) asks for a lattice vector \(\mathbf{v} \in \mathcal{L}\) minimizing \(\|\mathbf{v} - \mathbf{t}\|\); the minimum value itself is the distance \(\operatorname{dist}(\mathbf{t}, \mathcal{L})\). Three versions of the question sit at different strengths. The search version demands the nearest vector; the optimization version asks only for the distance \(\operatorname{dist}(\mathbf{t}, \mathcal{L})\) without exhibiting the vector; the decision version is weaker still, asking only whether \(\operatorname{dist}(\mathbf{t}, \mathcal{L}) \leq r\) for a supplied bound \(r\). These look like three problems of decreasing difficulty, and the first implication is immediate: a nearest vector hands you its own distance, and a distance settles any threshold question. The content is that the implications also run backward. A procedure that answers only the yes-or-no decision question can be called repeatedly — binary search over the distance, then a sequence of queries that sieves the lattice to sparser and sparser sublattices — to recover first the distance and then the vector itself, all in polynomially many calls. The three versions are therefore equivalent up to polynomial-time computation, which is why hardness may be studied on whichever version is most convenient, and why the decision version, being the simplest to reason about, is the one on which the complexity results are proved.

That decision version is genuinely hard, and here the hardness is not norm-dependent or probabilistic but flatly classical. Deciding whether a target lies within a given distance of a lattice is NP-complete. Membership in NP is the easy half: a lattice vector within distance \(r\) of the target is a certificate of the "yes" answer, checkable by a single distance computation, and short enough to write down because its entries are bounded by the target's size plus \(r\). The hard half exhibits a polynomial-time reduction from a problem already known to be NP-complete — the subset-sum problem, which asks whether some subset of a given list of integers \(a_1, \dots, a_n\) sums to a target \(S\). The reduction is clean enough to state in full.

The same combinatorial construction, adapted, yields NP-hardness of the exact shortest vector problem in the \(\ell_\infty\) norm — the norm-dependent claim promised earlier now has its source. In the Euclidean norm the corresponding statement for SVP demands considerably more, which is the asymmetry the previous section flagged. For the closest vector problem, though, the Euclidean case is already settled by the reduction above.

With CVP in hand as the hub, two specializations carry the actual cryptographic weight, and both are named objects the track will reuse. The first restricts the target to lie unusually close to the lattice — closer than half the minimum distance — so that the nearest vector is unique and the problem becomes one of decoding a point known to be a slight perturbation of a lattice point.

The promise is what distinguishes BDD from CVP. A general target may sit anywhere, with several lattice points nearly tied for closest; BDD guarantees the target is a small displacement of one particular lattice point, and asks only to recover it. The condition \(\operatorname{dist}(\mathbf{t}, \mathcal{L}) \lt \lambda_1 / 2\) already forces uniqueness — two lattice points within that distance of \(\mathbf{t}\) would sit within \(\lambda_1\) of each other, contradicting the definition of the minimum distance — and the factor \(\gamma\) tightens the promise further. This is the shape of a decryption problem: a ciphertext is a lattice point plus a small error, and recovering the message is recovering the lattice point. The encryption schemes the track builds toward are, at their core, instances of decoding under exactly such a promise.

The second specialization returns to the intrinsic geometry of the lattice, generalizing the first minimum from one short vector to a full set of them. A lattice of rank \(n\) has not just a shortest vector but a whole sequence of successive minima \(\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n\), where \(\lambda_i\) is the smallest radius within which the lattice contains \(i\) linearly independent vectors. Finding one short vector is SVP; finding a full independent set of them, all short, is its natural generalization.

SIVP asks for a basis-like object that is short in the strong sense that even its longest member is controlled by the \(n\)-th successive minimum. It is the problem that most directly captures "find a good basis," and it is the worst-case problem to which the security of the lattice encryption schemes will ultimately be tied. That tie — a guarantee that breaking the average-case encryption problem would entail solving SIVP (and its decision-style companion, introduced next) in the worst case — is the feature that sets lattice cryptography apart, and it is why SIVP earns a name here even though nothing on this page yet uses it. The definitions of this section are the vocabulary; the hierarchy that orders them by difficulty, and locates the cryptographic sweet spot among them, is the work of the next.

The Approximation Hierarchy

The problems of the previous sections were posed as search or promise tasks with an approximation factor \(\gamma\) attached. To speak about their complexity in the sharpest terms — membership in classes like NP, and its complement — it helps to recast the approximate problems in decision form, as promise problems. A promise problem does not partition all inputs into yes and no; it guarantees that every input it is asked about falls into one of two well-separated cases, and asks an algorithm only to tell those two apart. The gap between the cases is exactly the approximation factor.

The companion problem \(\mathrm{GapCVP}_\gamma\) is defined identically but for a target: given \(\mathbf{B}\), a target \(\mathbf{t}\), and a bound \(r\), a YES instance has \(\operatorname{dist}(\mathbf{t}, \mathcal{L}) \leq r\) and a NO instance has \(\operatorname{dist}(\mathbf{t}, \mathcal{L}) \gt \gamma r\). At \(\gamma = 1\) the promise gap closes and \(\mathrm{GapCVP}_1\) is exactly the decisional closest vector problem shown NP-complete above. Increasing \(\gamma\) widens the gap, weakens the problem, and is what makes the higher rungs of the hierarchy tractable.

The first structural fact orders the two families against each other: approximating shortest vectors is no harder than approximating closest ones. This is the promised inheritance of hardness, and the reduction realizing it is short.

The reduction preserves the gap \(\gamma\) exactly and calls the oracle on lattices of the same rank as the input — it is gap-preserving and rank-preserving, features that make it a reliable tool elsewhere. It calls the oracle \(n\) times rather than once, so it is a Turing-style reduction rather than the single-instance mapping used for the NP-completeness above; whether a single-instance reduction exists is not known. The consequence for the hierarchy is what matters: any complexity upper bound proved for \(\mathrm{GapCVP}_\gamma\) transfers to \(\mathrm{GapSVP}_\gamma\), because a solver for the former yields one for the latter.

With the two families linked, the hierarchy can be read off as a function of the one parameter \(\gamma\). Three regimes divide the line, and the boundaries between them are where the whole subject lives.

At the bottom, for small approximation factors, the problems are NP-hard. Exact GapCVP is NP-complete, and the hardness persists as the gap opens, degrading only slowly; approximating the closest vector to within almost-polynomial factors — factors below any fixed power of the dimension — remains NP-hard. Any algorithm solving the problem for these gaps would solve every problem in NP.

At the top, for factors that grow exponentially in \(n\), the problems are solvable in polynomial time. This is the domain of basis reduction, the subject of the final section: a polynomial-time procedure exists that finds a vector within an exponential factor of the shortest, and no better. The exponential-approximation regime is the easy end of the line.

Between these lies the regime that cryptography occupies, and its defining feature is a negative one: for gaps around \(\sqrt{n}\), the problems are almost certainly not NP-hard. The evidence is a containment. For \(\gamma = \sqrt{n}\), the problem \(\mathrm{GapCVP}_{\sqrt{n}}\) lies not only in NP but in its complement coNP — meaning a NO instance, one where the target is far from the lattice, admits a short certificate of its farness, just as a YES instance admits a nearby lattice vector as certificate of its nearness. Certifying farness is the hard direction: a target can have enormously many lattice points near it without any being within the bound, and exhibiting a succinct proof that none is close is not obvious. The earliest arguments that farness can be certified went through the dual lattice — the reciprocal lattice whose geometry, tied to the original by the reciprocal determinant relation, converts a statement about the absence of short vectors on one side into the presence of a witness on the other. An early argument of this kind reached the smaller gap \(\sqrt{n / \log n}\), placing the problem there in a probabilistic analogue of coNP; later work sharpened the containment, widening the gap to \(\sqrt{n}\) and strengthening the class to coNP proper. By the reduction just proved, all of this transfers to \(\mathrm{GapSVP}\): the shortest vector problem at gap \(\sqrt{n}\) is likewise in \(\mathrm{NP} \cap \mathrm{coNP}\).

The force of this containment is what it forbids. A problem that is NP-hard and simultaneously in coNP would place all of NP inside coNP, collapsing the tower of complexity classes above them — the polynomial hierarchy — to a low level, an outcome complexity theorists regard as most unlikely. So the containment of \(\mathrm{GapSVP}_{\sqrt{n}}\) in \(\mathrm{NP} \cap \mathrm{coNP}\) is read in reverse, as a ceiling on hardness: the NP-hardness that holds for small gaps cannot be pushed up to the gap \(\sqrt{n}\) without collapsing the hierarchy. Approximating lattice vectors to within \(\sqrt{n}\) is, in all likelihood, strictly easier than the NP-hard exact problem — and yet no efficient algorithm for it is known.

The hierarchy thus delivers a single object, \(\mathrm{GapSVP}_\gamma\) with its shadow \(\mathrm{GapCVP}_\gamma\), whose difficulty is dialed by one parameter from NP-hard to polynomial-time, and it locates the cryptographic regime as a plateau near \(\sqrt{n}\) — above the reach of every known algorithm, below the NP-hardness ceiling that the polynomial hierarchy protects. What remains is to see the one algorithm that does reach the lattice, understand exactly how far up it climbs, and confront the fact that a quantum computer climbs no higher.

What the Quantum Attack Leaves Standing

The hierarchy left one algorithm unexamined: the procedure that actually reaches into a lattice and returns a short vector. Every practical attack on a lattice problem, and every honest assessment of how hard these problems are, passes through basis reduction, introduced above. The foundational reduction algorithm runs in time polynomial in the dimension and the size of the input, and it always succeeds in producing a reduced basis. The question is how short the vector it returns actually is.

The answer is what everything downstream turns on. Basis reduction finds a vector guaranteed to be short — but only to within a factor that grows exponentially with the dimension. In the language of the hierarchy, the polynomial-time algorithm solves \(\mathrm{SVP}_\gamma\) for \(\gamma\) exponential in \(n\), and no better. It sits exactly at the tractable top of the hierarchy and does not descend into the middle. Improvements that trade running time for a smaller factor exist, but they buy only modest reductions in the exponent at steep cost, and none brings the approximation factor down to the polynomial range where the cryptographic problems live. The plateau near \(\sqrt{n}\) remains, after decades, out of reach.

This is the observation on which the security of every lattice construction rests, and it must be stated with care. The gap between what basis reduction achieves — an exponential approximation — and what would break the cryptography — a polynomial one — is not a theorem that the polynomial regime is hard. It is the absence of any algorithm that closes the gap. Lattice hardness, like the hardness of factoring before it, is a conjecture: the assertion that no efficient procedure approximates lattice vectors to within polynomial factors, supported by the failure of sustained effort to find one, not by a proof that none can exist.

What makes this conjecture the foundation for a post-quantum cryptography is a second fact, and it is the one this whole track has been moving toward. The classical assumptions fell to a quantum computer because factoring and the discrete logarithm carry a hidden periodic structure — an abelian arithmetic that a quantum procedure detects in polynomial time, collapsing the asymmetry the schemes depended on. Basis reduction is where one looks for the analogous quantum advantage against lattices, and the finding is stark: the best quantum algorithms for the lattice problems achieve the same exponential approximation as the best classical ones, and no better. Quantum computation buys no improvement in the approximation factor. No quantum algorithm approaches the polynomial gaps either.

The reason is structural, and it closes a thread left hanging by the quantum attack itself. Shor's algorithm succeeds by finding a period in an abelian group — the structure the number-theoretic problems supply and the lattice problems do not. A lattice has no such abelian period for a quantum procedure to seize; its shortest vectors are hidden by high-dimensional geometry, not by a hidden subgroup of the kind the quantum Fourier transform is built to expose. This is why the migration documented across the classical pages heads here specifically. It is not that lattices are provably beyond quantum reach — the honest claim is narrower and is the same conjectural shape as before: no efficient quantum algorithm for these problems is known, and the structure that made the classical problems fall is absent. The absence of a known attack, classical or quantum, is precisely what a post-quantum foundation is built from.

What remains is to build the encryption on this ground: to turn a worst-case lattice problem into the random-looking, average-case problem an encryption scheme can sample from, and to show that breaking the scheme would solve the worst-case problem underneath. That construction is where the geometry of this page becomes a working cryptosystem.