Lattice Cryptography Does Not Rest on NP-Hardness but on a Cost Estimate — Epoche B2
Re-evaluating Classical Security in Post-Quantum Cryptography Lattice-based key exchange and signatures are now standardised, and the case for them is usually put in one line: they rest on NP-hard problems, so classically they are at least as safe as the factoring and discrete-logarithm schemes they replace. Both halves of that sentence deserve inspection. This review argues that the NP-hardness label attaches to a parameter regime the schemes do not use, and that what actually protects a deployed lattice scheme is something different in kind — a calibrated cost estimate for one family of algorithms, expressed through a single attack parameter, the block size $\beta$ of lattice reduction. That is not a weaker claim in practice, but it is a claim of a different type, and confusing the two makes the security of post-quantum cryptography look more settled than it is. The problem the schemes stand on A lattice is the set of integer combinations of $n$ linearly independent basis vectors $\mathbf{b}_1,\dots,\mathbf{b}_n$ in $\mathbb{R}^{m}$, and its first minimum is the length of its shortest non-zero vector: $$ \mathcal{L}(\mathbf{B})=\Big\{\sum_{i=1}^{n}x_i\,\mathbf{b}_i \;:\; x_i\in\mathbb{Z}\Big\}, \qquad \lambda_1(\mathcal{L})=\min_{\mathbf{v}\in\mathcal{L}\setminus\{\mathbf{0}\}}\lVert\mathbf{v}\rVert . $$ The same lattice has infinitely many bases, some nearly orthogonal and some wildly skewed, and finding a short vector from a skewed basis is the computational problem. In its approximate form, $\mathrm{SVP}_\gamma$ asks for any lattice vector within a factor $\gamma$ of optimal: $$ \mathbf{v}\in\mathcal{L}\setminus\{\mathbf{0}\},\qquad \lVert\mathbf{v}\rVert\;\le\;\gamma\,\lambda_1(\mathcal{L}),\qquad \gamma=\gamma(n)\ge 1 . $$ Everything turns on $\gamma$. At $\gamma=1$ the problem is exact SVP, and Ajtai proved it NP-hard under randomised reductions [1] ; Khot extended the hardness to every constant $\gamma$ [2] . This is the result the slogan invokes, and it is genuine. Why the NP-hardness does not reach the deployed parameters The trouble is that no cryptosystem is built on constant $\gamma$. The assumption the standardised schemes actually rest on is Learning With Errors (LWE): given a uniformly random matrix and the noisy products $$ \mathbf{b}\;=\;\mathbf{A}\mathbf{s}+\mathbf{e}\ \bmod q, \qquad \mathbf{A}\in\mathbb{Z}_q^{m\times n},\quad \mathbf{s}\in\mathbb{Z}_q^{n},\quad e_i\leftarrow\chi_\sigma , $$ recover the secret $\mathbf{s}$. Here $n$ is the secret dimension, $q$ the modulus, $m$ the number of samples, and $\chi_\sigma$ a narrow error distribution of standard deviation $\sigma$, conventionally written $\sigma=\alpha q/\sqrt{2\pi}$ so that the noise parameter $\alpha$ measures the error relative to the modulus. Delete $\mathbf{e}$ and this is Gaussian elimination; the errors are the whole difficulty. Regev's theorem ties LWE to lattices [3] , and the direction it runs in is exactly the point. Worst-case $\mathrm{GapSVP}_\gamma$ and $\mathrm{SIVP}_\gamma$ with $\gamma=\tilde{O}(n/\alpha)$ reduce to average-case LWE: an efficient LWE solver would yield an efficient solver for those worst-case lattice problems [4] , which is what makes the assumption credible, and not the reverse. (Regev's reduction is quantum; Peikert later gave a classical variant for GapSVP at an exponentially large modulus [5] .) But the approximation factor it delivers is polynomial in the dimension, and at those factors the complexity picture changes qualitatively. Here $\mathrm{GapSVP}_\gamma$ is the decision form of the problem: given a lattice and a length $r$, decide whether $\lambda_1(\mathcal{L})\le r$ or $\lambda_1(\mathcal{L})\gt\gamma r$, with no answer demanded in between. Goldreich and Goldwasser showed that it lies in $\mathrm{NP}\cap\mathrm{coAM}$ &mdash [6] ; both yes- and no-instances admit short interactive proofs — once $\gamma\ge\sqrt{n/\log n}$, and Aharonov and Regev sharpened that containment to $\mathrm{NP}\cap\mathrm{coNP}$, at the slightly larger factor $\gamma\ge\sqrt{n}$. Setting their result beside Ajtai's and Khot's hardness theorem from the previous section puts the two regimes side by side: $$ \gamma=O(1)\ \implies\ \text{SVP}_\gamma\ \text{is NP-hard}; \qquad \gamma\ge\sqrt{n}\ \implies\ \text{GapSVP}_\gamma\in\text{NP}\cap\text{coNP} . $$ A problem in $\mathrm{NP}\cap\mathrm{coNP}$ cannot be NP-hard unless $\mathrm{NP}=\mathrm{coNP}$, which would collapse the polynomial hierarchy — the tower of complexity classes built above NP by alternating quantifiers — down to its first level, and nobody expects that. So the two statements are not two views of one guarantee: the hardness theorem lives at $\gamma=O(1)$, the schemes live at $\gamma=\mathrm{poly}(n)$, and the containment above blocks the transport of the theorem from the one regime to the other. That block is conditional, and the essay's own thesis obliges it to say so: the membership $\mathrm{GapSVP}_\gamma\in\mathrm{NP}\cap\mathrm{coNP}$ is proved outright, but the impossibility of NP-hardness follows from it only if $\mathrm{NP}\ne\mathrm{coNP}$. (Whether average-case instances inherit worst-case difficulty is a further question, and a separate one.) What is left is not nothing — it is a large body of evidence that no algorithm achieves polynomial approximation factors in polynomial time — but the evidence is algorithmic and quantitative rather than complexity-theoretic, and it is measured, not proved. What is actually measured: reduction quality Lattice reduction algorithms are graded by how short a first basis vector they return, normalised against the lattice determinant. The standard measure is the root-Hermite factor $\delta_0$, defined by $$ \lVert\mathbf{b}_1\rVert\;\le\;\delta_0^{\,n-1}\;\det(\mathcal{L})^{1/n} . $$ Because $\delta_0$ is raised to the power $n$, a change in the third decimal place is an enormous change in attack capability at cryptographic dimensions. The workhorse algorithm is BKZ, which r