# Why do we add error in the definition of LWE?

One of the various equivalent definitions of the LWE problem is the following:

Let $$n,q$$ be integers ($$q$$ usually is a prime number), $$\chi$$ a discrete probability distribution over $$\mathbb{Z}$$ (usually a discrete Gaussian distribution) and $$s$$ a secret vector from $$\mathbb{Z}_q^n$$.

We denote $$\mathcal{L}_{s,\chi}$$ the probability distribution over $$\mathbb{Z}_q^n \times \mathbb{Z}_q$$ obtained by choosing $$a \in \mathbb{Z}_q^n$$ uniformly at random, choosing $$e$$ uniformly at random from $$\chi$$ and considering it in $$\mathbb{Z}_q$$, and calculating $$(a,b=(\langle a,s\rangle + e)) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$$.

The Search Learning With Errors is to recover $$s$$ from samples $$(a,b)$$ obtained from $$\mathcal{L}_{s,\chi}$$.

My questions is why do we add the error $$e$$? I suppose that it is for security reasons. In that case, how we would be able to obtain $$s$$ from $$(a,b=(\langle a,s\rangle))$$?

Since adding some error $$e$$ is a central block in a lot of lattice-based constructions, this could be a more general question. What is the point of adding this error?

In that case, how we would be able to obtain $$s$$ from $$(a,b=(\langle a,s\rangle))$$?

The operation $$\langle a,s\rangle$$ is a matrix multiplication, that is, completely linear, and hence Gaussian elimination allows us to recover $$s$$ efficiently.

• Another reason is indistinguishability. – kelalaka Jul 2 at 18:13
• Can you expand this answer? The value $\langle a,s\rangle$ is just one inner product, so it’s not enough information to recover $s$ uniquely (when $n>1$). We would need many samples (at least $n$) from the distribution to get invertible matrix multiplication. – Chris Peikert Jul 3 at 11:22