Noise Breaks Linear Algebra

The chapter now leaves the plane and moves into modular arithmetic. The transition is abrupt, and it is worth saying in advance where it is going: we are about to build a problem that looks like schoolbook simultaneous equations, and then break it with a single unit of noise.

Simultaneous equations modulo $q$ are easy

Suppose there is a secret vector $s$ with $n$ components, all of them in $\mathbb{Z}_q$, and an attacker gets to see equations of the form

$$\langle a_i, s \rangle \;\equiv\; b_i \pmod q, \qquad i = 1, 2, \ldots, n,$$

where each $a_i$ is a known vector and each $b_i$ is a known number.

The angled brackets are the inner product, sometimes called the dot product, and it means multiply componentwise and add:

$$\langle (1, 4, 3),\; (5, 11, 2) \rangle \;=\; 1 \cdot 5 + 4 \cdot 11 + 3 \cdot 2 \;=\; 5 + 44 + 6 \;=\; 55 .$$

Stack the $n$ equations into a matrix statement:

$$A s \;\equiv\; b \pmod q .$$

This is a system of linear equations, and solving it is a schoolbook exercise. If $A$ is invertible modulo $q$, which is likely when $q$ is prime, then

$$s \;=\; A^{-1} b \bmod q$$

and the attacker has the secret. One matrix inversion, done in time cubic in $n$. For $n = 256$ that is a few million operations, meaning milliseconds.

So this is no basis for a cryptosystem at all. Publishing $A$ and $b$ publishes $s$.

02.Adding the noise

Now change one thing. Add a small error to each equation:

$$b_i \;=\; \langle a_i, s \rangle + e_i \bmod q ,$$

where each $e_i$ is a small integer, drawn from some distribution concentrated near zero. Small means genuinely small. In the example below, $e_i$ is one of $-1$, $0$ or $+1$.

The attacker now sees equations that are each almost right and none of which is exactly right.

The natural first reaction is that this cannot possibly matter much. The errors are tiny, the equations are nearly correct, so surely the solution comes out nearly correct, and rounding fixes it.

That reaction is wrong, and the reason is worth understanding properly.

03.Why a tiny error is not a tiny problem

Gaussian elimination, the standard method, works by multiplying equations by constants and adding them together. Modulo $q$, those constants are elements of $\mathbb{Z}_q$, and they are not small. Eliminating a variable might require multiplying an entire equation by $11$, or by $3329$.

When you multiply an equation by $11$, you multiply its error by $11$ too.

Do this a few dozen times, as elimination on a $256 \times 256$ system requires, and the accumulated error is no longer small. It has been multiplied and summed until it wraps around the modulus repeatedly. At that point the error is indistinguishable from a uniformly random element of $\mathbb{Z}_q$, and the equation it is attached to carries no information at all.

There is a second way to see it. Modular arithmetic has no notion of "close". In Modular Arithmetic the residues are a clock face, and $16$ is adjacent to $0$ modulo $17$ just as much as $1$ is. There is no ordering to be nearly right about. So "the answer came out slightly off" is not a recoverable situation the way it would be with real numbers. Slightly off in $\mathbb{Z}_q$ means somewhere else entirely.

04.The demonstration

Assertions are cheap. Here is the arithmetic.

Take $q = 17$, $n = 3$, and the secret

$$s \;=\; (5,\, 11,\, 2) .$$

Take three known vectors and stack them:

$$A \;=\; \begin{pmatrix} 1 & 4 & 3 \\ 2 & 0 & 7 \\ 6 & 9 & 12 \end{pmatrix} .$$

Compute the three exact inner products.

$$\langle (1,4,3), s \rangle = 5 + 44 + 6 = 55 \equiv 4 \pmod{17},$$

since $55 = 3 \cdot 17 + 4$.

$$\langle (2,0,7), s \rangle = 10 + 0 + 14 = 24 \equiv 7 \pmod{17},$$ $$\langle (6,9,12), s \rangle = 30 + 99 + 24 = 153 \equiv 0 \pmod{17},$$

since $153 = 9 \cdot 17$ exactly.

Without noise. The attacker sees $b = (4, 7, 0)$. Inverting $A$ modulo $17$ and multiplying gives

$$A^{-1} b \;=\; (5,\, 11,\, 2) \bmod 17,$$

which is $s$, exactly. The secret is recovered in one step, as promised.

With noise. Now add errors $e = (+1,\, 0,\, -1)$, each of them as small as a non-zero error can be. The attacker sees

$$b' \;=\; (4 + 1,\;\; 7 + 0,\;\; 0 - 1) \;=\; (5,\; 7,\; 16) \bmod 17,$$

noting that $-1 \equiv 16 \pmod{17}$.

Run the identical computation on $b'$:

$$A^{-1} b' \;=\; (13,\, 14,\, 7) \bmod 17 .$$

Compare that with the true secret $(5, 11, 2)$.

Not one component is right. The first is off by $8$, the second by $3$, the third by $5$. The answer is not a slightly perturbed version of the secret that could be cleaned up by rounding. It is an unrelated point in $\mathbb{Z}_{17}^3$, and there are only $17^3 = 4913$ of those, so a wrong answer here is worth about as much as a guess.

That is the entire idea of Learning With Errors, visible in a $3 \times 3$ system. Three errors of magnitude at most one destroyed the solution completely.

05.What the attacker is left with

If elimination is useless, what can an attacker actually do?

They can search. Somewhere out there is a vector $s$ and a small error vector $e$ satisfying $b = As + e$, and the error is small. So the attacker is looking for a point $As$ that is unusually close to the observed $b$.

That is the closest vector problem from Short Vectors: SVP and CVP, on a lattice built out of $A$. The next note makes the connection precise.

And this is why the chapter spent five notes on geometry before touching cryptography. The noise did not merely make the equations harder to solve. It converted a linear algebra problem, which is easy, into a lattice problem, which is not.