Lattice Problems

The Shortest Vector Problem

The starting point is the lattice, built as a geometric object: the set of all integer combinations of a basis, which forms a discrete additive subgroup of \(\mathbb{R}^n\). From that geometry the previous pages extracted a single number that measures how tightly the lattice packs space near the origin. That number is the length of its shortest nonzero vector, the minimum distance \(\lambda_1(\mathcal{L})\). Everything on those pages was about the existence of a short vector. Minkowski's convex body theorem guaranteed one without ever producing it. Minkowski's first theorem, its corollary for full-rank lattices, delivers 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, so 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 the shortest vector, the geometric information that a badly chosen basis obscures. A cryptographic construction can exploit exactly this, by publishing a bad basis and keeping 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 can be posed in the \(\ell_\infty\) norm, where a vector's length is its largest coordinate in absolute value. It behaves differently there, 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 whose radius is of the order that the Minkowski bound allows can grow exponentially with \(n\). The shortest vector can also hide among integer combinations whose coefficients are individually large even when the vector they produce is small, and 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. Conversely, hardness is more naturally established for the approximate problem than for 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 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 exact SVP 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, an argument beyond the scope of this page.

In short, exact SVP is hard in both norms, but considerably harder to prove hard in the Euclidean one. As the hierarchy will make precise, however, the hardness that actually supports cryptography is not this worst-case exact hardness at all. It is 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 this problem precisely but, unlike SVP, do not give it a formal definition. The choice reflects its role. The cryptographic constructions built on lattices 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 and asks only whether \(\operatorname{dist}(\mathbf{t}, \mathcal{L}) \leq r\) for a supplied bound \(r\).

The three versions look like problems of decreasing difficulty, and the implications in that direction are immediate. A nearest vector yields 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 to recover first the distance and then the vector itself, all in polynomially many calls. The distance comes from binary search over the bound \(r\), and the vector from a sequence of queries that sieves the lattice to sparser and sparser sublattices. We omit the details of that sieve. The three versions are therefore equivalent up to polynomial-time computation. Hardness may thus be studied on whichever version is most convenient, and the complexity results are proved for the decision version, the simplest to reason about.

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 certificate of the "yes" answer is the integer coefficient vector \(\mathbf{x}\) of a lattice point \(\mathbf{B}\mathbf{x}\) within distance \(r\) of the target, and checking it takes one matrix-vector product and one distance computation. That some such \(\mathbf{x}\) has polynomially many bits follows from a routine size estimate, which we do not carry out here. Each entry of the point \(\mathbf{B}\mathbf{x}\) lies within \(r\) of the corresponding entry of the target, and \(\mathbf{x}\) is recovered from it by solving a linear system. The hard half exhibits a polynomial-time reduction from 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\). Subset-sum is NP-complete, a fact we take from complexity theory without proof, and the reduction is clean enough to state in full.

An adaptation of the same combinatorial construction, whose details we omit, yields NP-hardness of the exact shortest vector problem in the \(\ell_\infty\) norm. This is the source of the norm-dependent claim made earlier. 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 receive formal definitions. The first restricts the target to lie unusually close to the lattice, closer than half the minimum distance. The nearest vector is then 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 that 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 lie at distance less than \(\lambda_1\) from each other, contradicting the definition of the minimum distance. 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. Lattice-based encryption schemes 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 is the feature that sets lattice cryptography apart: a guarantee about the worst case. An efficient attack on the average-case encryption problem would yield an efficient algorithm, possibly a quantum one, for SIVP and for its decision-style companion introduced next, at polynomial approximation factors and on every lattice. SIVP therefore earns a name here even though nothing on this page uses it yet. 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 section.

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, such as membership in NP and in 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 lies in 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 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. Upper bounds proved for \(\mathrm{GapCVP}_\gamma\) transfer to \(\mathrm{GapSVP}_\gamma\). An efficient solver for the former yields one for the latter, and certificates transfer as well, because a YES answer needs one YES among the \(n\) oracle instances and a NO answer needs all \(n\) of them to be NO.

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. The results that place each regime are deep, and apart from the reduction just proved we state them without proof.

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 remains NP-hard even to within factors of the form \(n^{c/\log \log n}\) for a constant \(c \gt 0\), which grow faster than any constant yet more slowly than any fixed power of the dimension. An efficient algorithm solving the problem for these gaps would yield efficient algorithms for 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. From gaps around \(\sqrt{n}\) upward, 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. Membership in coNP means that 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 first certificates of farness went through the dual lattice. The dual is 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. Those first arguments placed the problem in coNP only at gaps larger than \(\sqrt{n}\). A different, interactive argument later reached the smaller gap \(\sqrt{n / \log n}\), placing the problem there in a probabilistic analogue of coNP. Containment in coNP proper at the gap \(\sqrt{n}\) came afterward, again through the dual lattice. By the reduction just proved, the containment at \(\sqrt{n}\) 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. The tower of complexity classes built above them, the polynomial hierarchy, would then collapse to its first 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. 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. It also locates the cryptographic regime as a plateau of polynomial gaps, from \(\sqrt{n}\) upward. That plateau lies below the reach of every known algorithm and above the ceiling that bounds NP-hardness, a ceiling that holds unless the polynomial hierarchy collapses.

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.

Everything that follows turns on the answer. 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, in polynomial time, to the polynomial range where the cryptographic problems live. The plateau of polynomial gaps remains, after decades, out of reach.

The security of every lattice construction rests on this observation, and it must be stated with care. Basis reduction achieves an exponential approximation. Breaking the cryptography would need a polynomial one. The gap between the two is not a theorem that the polynomial regime is hard. It is the absence of any known 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. The classical assumptions fell to a quantum computer because factoring and the discrete logarithm carry a hidden periodic structure. That structure is an abelian arithmetic that a quantum procedure detects in polynomial time, and detecting it collapses the asymmetry the schemes depended on. Basis reduction is where one looks for the analogous quantum advantage against lattices, and the finding is stark. For general lattices, the best known polynomial-time quantum algorithms achieve the same exponential approximation as the best classical ones, and none approaches the polynomial gaps.

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, a structure that 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.

That missing structure is why the search for quantum-resistant foundations heads to lattices specifically. Lattices are not provably beyond quantum reach. The honest claim is narrower and has 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.