The True Security of Lattice-Based Cryptography — Epoche B2
Beyond NP-Hardness: The True Security of Lattice-Based Cryptography The security of many classical public-key cryptosystems, such as RSA and Elliptic Curve Cryptography (ECC), relies on the presumed computational hardness of certain mathematical problems. For instance, RSA's security hinges on the difficulty of integer factorisation, while ECC depends on the discrete logarithm problem. Often, students new to cryptography might assume that the security of lattice-based schemes similarly derives from the NP-hardness of underlying lattice problems like the Shortest Vector Problem (SVP [1] ). Exact SVP is indeed NP-hard [2] , but that fact does almost none of the work here: at the approximation factors cryptography actually uses, the lattice problems in play are provably not NP-hard unless the polynomial hierarchy collapses, as we shall see. What underpins the exceptional strength and post-quantum resilience of lattice-based cryptography is something else: the worst-case to average-case reduction. This essay clarifies that the security of lattice-based cryptography stems not merely from NP-hardness, but from the crucial reduction of worst-case to average-case hardness, which is vital for post-quantum resilience. The Cryptographic Need for Average-Case Hardness For a computational problem to serve as a reliable foundation for cryptography, it is not sufficient for only its most difficult, "worst-case" instances to be hard to solve. Cryptographic schemes typically generate problem instances randomly or semi-randomly, meaning that an adversary will encounter "average-case" instances. If these average-case instances are easy to solve, even if worst-case instances are hard, the cryptographic system is vulnerable. This is the challenge of "weak keys": specific instances of the problem that are much easier to break than the general case. Many NP-hard problems, while intractable in their worst-case, might have average-case instances that are considerably easier, or even trivial. Without a guarantee that the average-case instances are hard, a cryptosystem built on such a problem could be catastrophically compromised. It is tempting to say that traditional cryptosystems simply lack such a guarantee. That is not true, and the real difference is subtler and more interesting. Both RSA and the discrete logarithm are random self-reducible , which is precisely a worst-case to average-case reduction. Fix an RSA modulus $N$ and public exponent $e$, and suppose an oracle inverts the map $x \mapsto x^e$ on some non-negligible fraction of inputs. To invert an arbitrary $y = x^e \bmod N$, draw $r$ uniformly from $\mathbb{Z}_N^{*}$ and hand the oracle the blinded value $$ y' = y \cdot r^{e} \bmod N = (xr)^{e} \bmod N, \qquad r \in \mathbb{Z}_N^{*} \text{ uniform} $$ Since $r$ is uniform so is $y'$, the oracle returns $xr$, and multiplying by $r^{-1}$ recovers $x$. The same blinding works for discrete logarithms: given $Q = kP$ in a group of known prime order $N$ generated by $P$, hand the oracle $Q + rP = (k+r)P$ for uniform $r \in \mathbb{Z}_N$ and subtract $r$. Breaking either problem on a non-negligible fraction of inputs therefore breaks it on all of them. What separates lattice cryptography is the level at which its reduction operates. Both self-reductions are confined to one fixed modulus or group: they say that all instances within a given $N$ are equally hard, and nothing about whether a randomly generated modulus or curve is as hard as the hardest one. That is exactly where weak-key risk lives — in parameter generation, not in the choice of challenge. The lattice reduction instead runs from the worst case of a different problem to the average case of Learning With Errors (LWE) — the noisy linear-equations problem defined two sections below — across the whole parameter space, covering the generation step that random self-reducibility leaves untouched. Lattices and the Shortest Vector Problem (SVP) To understand this reduction, we first need to define what a lattice is and introduce the hard problems associated with them. A lattice $\mathcal{L}$ is a discrete set of points in $m$-dimensional Euclidean space, $\mathbb{R}^m$, that forms a regular, repeating structure. It can be formally defined by a basis $B = \{\mathbf{b}_1, \dots, \mathbf{b}_n\}$ consisting of $n$ linearly independent vectors in $\mathbb{R}^m$. Any vector in the lattice is an integer linear combination of these basis vectors: $$ \mathcal{L}(B) = \left\{ \sum_{i=1}^n x_i \mathbf{b}_i \mid x_i \in \mathbb{Z} \right\} $$ Here, $n$ is the dimension or rank of the lattice, and $m$ is the dimension of the ambient space, where $m \ge n$. The coefficients $x_i$ are integers, and $\mathbf{b}_i \in \mathbb{R}^m$ are the basis vectors. Different bases can generate the same lattice, but some bases are "good" (consisting of short, nearly orthogonal vectors) while others are "bad" (consisting of long, skewed vectors). One of the most fundamental computational problems on lattices is the Shortest Vector Problem (SVP). Given a basis $B$ for a lattice $\mathcal{L}$, SVP asks for a non-zero vector $\mathbf{v} \in \mathcal{L}$ that has the minimum possible Euclidean norm (length). The length of this shortest non-zero vector is denoted $\lambda_1(\mathcal{L})$: $$ \lambda_1(\mathcal{L}) = \min_{\mathbf{v} \in \mathcal{L}, \mathbf{v} \ne \mathbf{0}} \|\mathbf{v}\|_2 $$ where $\|\mathbf{v}\|_2 = \sqrt{\sum v_i^2}$ is the Euclidean norm of vector $\mathbf{v}$. Exact SVP in the Euclidean norm is NP-hard under randomised reductions (Ajtai, 1998), a caveat never since removed. NP-hardness means every problem in $\mathsf{NP}$ reduces to it in polynomial time: a statement about reducibility, not about algorithms, which rules out a polynomial-time algorithm only if $\mathsf{P} \ne \mathsf{NP}$. For cryptographic purposes, we often consider approximation versions, such as the GapSVP$_{\gamma}$ problem. Given a lattice $\mathcal{L}$ and an approximation factor $\gamma \g