Learning With Errors, Read Twice

A Linear System, Read Twice

Two of the most heavily used objects in this curriculum turn out to share a strikingly similar syntactic structure. On one side sits the workhorse of statistical learning: a linear model observed through noise. On the other sits one of the hardness assumptions underwriting post-quantum encryption. They live in different worlds, one continuous, the other reduced modulo \(q\), but the sentence that describes them is nearly the same.

Recall the linear regression model, the starting point of nearly every supervised method we have built. To it we add the noise model under which least squares is the maximum-likelihood estimator, taking the residual \(\boldsymbol{\epsilon}\) to be Gaussian: \[ \mathbf{Y} = X\boldsymbol{\beta} + \boldsymbol{\epsilon}, \quad \boldsymbol{\epsilon} \sim \mathcal{N}(\mathbf{0}, \sigma^2 I). \] A design matrix \(X\) acts on an unknown parameter vector \(\boldsymbol{\beta}\). We observe the product corrupted by a small amount of Gaussian noise, and the entire enterprise of regression is to recover \(\boldsymbol{\beta}\) despite that corruption.

Now recall the Learning With Errors distribution. A public matrix \(\mathbf{A}\) acts on a secret vector \(\mathbf{s}\). We observe the product, corrupted by a small error, and reduced modulo \(q\): \[ \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \pmod{q}, \quad \mathbf{e} \sim \chi. \] The error distribution \(\chi\) is, in that formulation, a discrete Gaussian of small width. The standardized schemes do not use one. They draw each coefficient from a centered binomial distribution on \(\mathbb{Z}_q\), governed by a small integer parameter, so that every error is bounded rather than merely unlikely to be large ([1]). The same distribution supplies the secret. This is a substitution, not a compromise. Up to the modular reduction, and the discreteness it forces, the two displays line up term for term.

The Two Readings, Side by Side

The two partings are of different kinds. The second, purpose, is a reversal of intent, not of structure. The vectors \(\boldsymbol{\beta}\) and \(\mathbf{s}\) occupy the same slot, and only our attitude toward them differs. The first, arithmetic, is structural, and it is the one that will do the work.

So the question writes itself. If LWE is noisy linear regression, and regression is something our models solve for a living, why is LWE considered hard enough to protect the world's data against a quantum adversary? The tension between those two readings is the entire content of this page, and it resolves into a single design parameter that the demo at the end places under the reader's hand.

The Estimation View

Read the LWE sample as data. We are handed rows \((\mathbf{a}_i, b_i)\) with \(b_i = (\langle \mathbf{s}, \mathbf{a}_i\rangle + e_i) \bmod q\), and we want the coefficient vector \(\mathbf{s}\). Over the reals, this is the problem least squares was invented to solve, and if the modulus were not there, an attacker would simply solve it. Without noise, enough independent rows determine \(\mathbf{s}\) exactly. With noise, they determine it only up to estimation error.

Penalized least squares supplies the vocabulary in which this reading becomes precise, and the vocabulary sorts the secrets into two regimes. A standard LWE secret is small but dense. Its coordinates are drawn from a narrow distribution centered at zero, and none of them is expected to vanish. Shrinking a dense coefficient vector toward the origin while keeping a noisy, ill-conditioned system solvable is what the \(\ell_2\) penalty does, and the closed form of the Ridge Regression Solution exhibits the mechanism directly. The added \(\lambda I\) restores invertibility without ever forcing a coordinate to zero.

Some deployments instead choose secrets that are small and sparse, with most of their coordinates exactly zero, because sparsity buys efficiency in homomorphic encryption. Over the reals, recovering such a vector is the regime the \(\ell_1\)-penalized Lasso Regression is built for, since its penalty pressures coordinates to zero rather than merely shrinking them. No one runs Lasso against a lattice scheme, and the next subsection explains why. Modular reduction destroys the convex geometry on which the \(\ell_1\) ball's sharp corners do their work.

What survives the crossing is not the algorithm but the accounting. Sparsity is extra structure, and an adversary able to exploit structure has strictly more to work with than one facing a dense unknown. The lattice attacks exploit that fact by their own means, in their own geometry. A secret chosen sparse for the sake of efficiency has, in the language of estimation, handed something away. That is a caution worth recording about a parameter choice, not a claim about the standardized schemes, whose secrets are dense.

Why the regression does not simply succeed

If LWE is regression, why can we not always run the regression? The obstruction is the single ingredient that the real-valued model lacks: reduction modulo \(q\). Over \(\mathbb{R}\), the least-squares objective \(\|\mathbf{Y} - X\boldsymbol{\beta}\|_2^2\) is a convex bowl, and every local step of an optimizer carries information about the global minimum. That is the mechanism by which regression works at all. Local gradient information is globally trustworthy. (The regression pages write this response vector as \(\boldsymbol{y}\). We keep \(\mathbf{Y}\) throughout, so that the estimation reading and the lattice reading of the same object share one symbol.)

Reduction modulo \(q\) destroys this. The map \(t \mapsto t \bmod q\) wraps the real line onto a circle, and a coefficient vector that is slightly wrong no longer produces a slightly wrong prediction. It produces a residual that has wrapped around, spread across \(\mathbb{Z}_q\) with no proximity to zero and no gradient pointing home.

It would be misleading to say that the resulting landscape is flat. Between wrap boundaries the objective is still a quadratic, still differentiable, still equipped with a perfectly well-defined gradient. The wrapping merely chops the single convex bowl into an enormous number of separate quadratic pieces and shuffles them. Each piece has a minimum, and none of those minima knows anything about the others. An optimizer standing at a near-miss sits in a bowl, descends confidently, and arrives somewhere with no relation to \(\mathbf{s}\). The gradient is not absent. It is uninformative, because the arithmetic has severed the link between "close to \(\mathbf{s}\)" and "small residual." This is the mechanism, stated without proof, by which a problem that looks like regression resists being solved like regression. The noise \(\mathbf{e}\) then does the finishing work. The exact secret produces a nonzero residual, so an attacker cannot verify a candidate by exact fit.

It would be a mistake, though, to conclude that a broken gradient is what keeps LWE safe, or that less noise is always better for the defender. Push the width toward zero and the samples stop being a hostile optimization landscape and start being a system of polynomial equations. Algebraic techniques solve such a system outright, in subexponential and sometimes polynomial time, once the error is small relative to the dimension. Those techniques demand a great many samples, which is one reason schemes are careful about how much they publish. But the lesson stands. The noise must be wide enough to destroy the algebraic structure, and narrow enough that honest ciphertexts still decode. The regression view sees only one of those two constraints.

The Homomorphism View

Now read the same structure the other way. Instead of trying to strip the noise away to recover \(\mathbf{s}\), suppose we embrace it, and ask what we can compute while the data stays hidden inside it. The answer is what lets lattice cryptography underwrite essentially every practical scheme for computing on encrypted data.

The name is not an accident of jargon, but it points at a different map than one first expects. A ring homomorphism is a map \(\phi\) that preserves both operations, \(\phi(a + b) = \phi(a) + \phi(b)\) and \(\phi(ab) = \phi(a)\phi(b)\). It is tempting to say that encryption is such a map. It is not. Encryption is randomized, and the noise each ciphertext carries differs, so \(\mathrm{Enc}(m_1) \oplus \mathrm{Enc}(m_2)\) is not the same ciphertext as a fresh \(\mathrm{Enc}(m_1 + m_2)\). Neither identity holds.

The homomorphism runs the other way. It is \(\mathrm{Dec}\), carrying ciphertexts to plaintexts, that preserves the two operations exactly: \[ \mathrm{Dec}\big(\mathrm{Enc}(m_1) \oplus \mathrm{Enc}(m_2)\big) = m_1 + m_2, \quad \mathrm{Dec}\big(\mathrm{Enc}(m_1) \otimes \mathrm{Enc}(m_2)\big) = m_1 \cdot m_2, \] so \(\oplus\) and \(\otimes\) on ciphertexts descend to \(+\) and \(\cdot\) on plaintexts. Encryption is merely a randomized right inverse of \(\mathrm{Dec}\), which is precisely why the equalities fail upward and hold downward.

Two qualifications are essential. This \(\mathrm{Dec}\) is a partial map. It is a homomorphism only on the ciphertexts whose accumulated noise still lies below the decryption threshold, and outside that region it is not a homomorphism at all, it is simply wrong. The failure of \(\mathrm{Enc}\) to be a homomorphism is likewise not a defect to be repaired. A deterministic encryption satisfying both identities would leak equality of plaintexts. The randomness that breaks the upward identity is the same randomness that secures the scheme.

The practical consequence is the point. A server that never sees a plaintext can still add and multiply the hidden values, returning an encrypted result only its owner can open.

The Ring-LWE structure supplies exactly this. Its samples live not in a raw vector space but in a quotient ring \(R_q\), and the ring's own addition and multiplication are what the ciphertext operations \(\oplus, \otimes\) ride on. The secret and its discrete Gaussian error sit inside ring elements, so the ring supplies a multiplication of ciphertexts directly, rather than forcing it to be simulated by many scalar operations.

That multiplication is not free. The product of two ciphertexts is quadratic in the secret. Where a fresh ciphertext is decrypted by a linear expression in \(s\), the product requires the powers \(1, s, s^2\), and so carries one more component than it began with. A further step, called relinearization, uses an auxiliary key to bring the result back to a standard ciphertext under the original key. That step, together with the noise growth it must control, is the dominant cost of homomorphic multiplication.

It would be tidy to say that the hardness assumption an attacker confronts in the estimation view is the very one that powers computation in the defense view. It is not quite. The estimation view attacked LWE over \(\mathbb{Z}_q^n\). The ring supplies its multiplication only because we have moved to Ring-LWE over \(R_q\). That is the trade, and it is a real one. The Worst-Case Hardness of Ring-LWE buys its guarantee from \(\mathrm{SVP}_\gamma\) on ideal lattices. These form a proper subclass of lattices, carrying extra algebraic structure that a general lattice does not have. The ring gives us ciphertext multiplication and charges us a stronger assumption for it. Same family, not the same problem.

That price is felt keenly enough that the standardized schemes decline to pay it in full. Rather than a single ring element, their secret is a short vector of ring elements, multiplied against a small matrix of them. That middle setting keeps most of the ring's efficiency while resting on a lattice problem less special than the ideal case ([1]). We will not develop that variant here. It is enough to notice that the axis running from raw vectors to full rings is a dial, not a switch, and that a scheme's position on it is a deliberate choice between structure and the assumption structure costs.

One Noise, Two Readings

The hinge between the two views is a single quantity: the width of the error distribution \(\chi\). At a fixed dimension it is the only knob there is, and it does not turn cleanly. The two readings pull it in opposite directions.

One Knob, Opposite Directions

The attack column deserves care, and the toy below will mislead anyone who reads it too literally. With only a handful of equations, widening \(\chi\) really does destroy the attacker's target. The true secret stops being the unique minimizer of the residual, and no algorithm can single out what is no longer singular.

But that is a symptom of having too few samples, not a property of LWE. An attacker may harvest as many samples as it likes, and for any noise short of the modulus scale, enough of them restore the secret to being the unique solution, though the number required climbs steeply as \(\chi\) widens. Only when the error distribution approaches the uniform one on \(\mathbb{Z}_q\) does the answer truly cease to exist. At that point a sample carries essentially no information about \(\mathbf{s}\). Cryptographic parameters live nowhere near that regime.

So the estimation reading, pressed to its conclusion, reaches a verdict that sounds like a contradiction. As an inference problem, LWE is solvable. Gather sufficiently many equations and the secret is determined, uniquely and in principle. What defeats the adversary is not that the answer is missing but that it is unreachable. In the dimensions real schemes use, no known procedure locates it before the universe ends. Statistics tells us the answer exists. Complexity tells us we cannot have it.

This separation between what is determined and what is computable is not peculiar to cryptography. It appears throughout high-dimensional statistics and learning theory, where problems from sparse principal components to planted structures in random graphs are known or conjectured to admit an answer that no efficient algorithm can produce ([3]). Such a gap is usually an obstacle, the reason a method that should work does not. Lattice cryptography is what happens when someone builds on the obstacle deliberately. The entire construction is an engineered instance of a problem whose solution is guaranteed to exist and believed to be out of reach.

Attack and defense spend the same noise, but not at the same rate, and this is what the demonstration below is built to show. On the compute side the ruler is a plaintext slot, \(\Delta = q/P\). A wobble of half a slot already corrupts the answer. On the attack side, in this toy, the ruler is the modulus \(q\) itself. The consequence is a corridor spanning only a factor of about four, and one that never opens. At no width is the secret unidentifiable while the computation still reliably decodes.

But that corridor is an artifact of a four-dimensional secret with eight equations, and reading it as the shape of the real trade-off would invert the subject. Real schemes do not escape the corridor by tuning \(\chi\). They escape it by raising the dimension \(n\). Doing so leaves the secret perfectly well determined, and puts it beyond reach anyway, since the cost of finding it grows faster than any adversary can pay. The noise need only be wide enough to defeat the algebraic shortcuts that a nearly noiseless system would admit, and narrow enough that the ciphertexts still decode. Everything else is bought with dimension, which is why the hardness of the underlying lattice problems in high dimension is what the security ultimately rests on.