As a high level intuition, why is LWE without modular reduction easy to solve?

Question

The LWE conjecture states that, given $A \in \mathbb{Z}_q^{m \times n}$ and $A x + e$ for $x \in \mathbb{Z}_q^n, e \in \mathbb{Z}_q^n$ it's difficult to recover $x$, given that $e$ is sampled from a distribution concentrated around $0$. This might be a uniform distribution on $\{-\delta q, -\delta q+1, \dots, \delta q\}$ or a discrete Gaussian.

We could try working over the integers $\mathbb{Z}$ instead of $\mathbb{Z}_q$, also using a discrete Gaussian. However, this turns out to be insecure and, following Bootle et al, one can use the least squares estimator and try to recover the secret value of $x$ that way.

The one thing that I'm missing is: why does that approach fail when we work modulo $q$? We could try to repeat the same algebra over $\mathbb{Z}_q$ that we decide over $\mathbb{Z}$. Is there any intuition why LWE is easy over $\mathbb{Z}$ and hard over $\mathbb{Z}_q$?

For example, the intuition why dlog is easy over $\mathbb{Z}$ and hard over $\mathbb{Z}_q$ is that we can "cheat" by using the ring structure of $\mathbb{Z}$, which we don't have in generic groups. Is there anything like that for LWE?

Answer 1

As a complement to @Chao Sun's suggestion, let me propose the following handwavy explanation.

Let's say you collect samples by groups of $n$ each, so that you have a sequence of pairs $(A_i,b_i)$ with $b_i = A_i s + e_i$, where we can assume wlog that the A_i's are all invertible over $\mathbb{R}$. Then we have: $$s = A_i^{-1} b_i - A_i^{-1} e_i = v_i + \varepsilon_i.$$ The errors $e_i$ are bounded, and for typical distributions of $A$, you can prove (using concentration results on the singular values of $A_i$) that the operator norm of $A_i^{-1}$ is also bounded with overwhelming probability. The expectation of $\varepsilon_i$ is zero by symmetry, so the law of large numbers shows that the average $\frac1k \sum_{i=1}^k \varepsilon_i$ tends to 0 when $k$ grows. It follows that the average of the first $k$ b_i's converges to $s$ for large $k$, which lets you recover $s$ exactly seeing as it has integer coefficients (just round once the error term is less than $1/2$ in infinity norm).

[Note that the above is not a particularly good algorithm to recover $s$, and it is much better to use e.g. least squares, or other suitable techniques depending on the specific distributons of $A$ and $e$, but this is for illustration purposes.]

The same idea would not work modulo $q$ for at least two reasons. First, as noted by @Chao Sun, since $A$ is normally chosen as uniform mod $q$, it is not the case that $A_i^{-1}$ will be “bounded” in a useful sense. Second, it is not true that averaging out “small values” mod $q$ yields another small value, contrary to what happens over $\mathbb{R}$, so the law of large numbers argument falls apart.

Of course, if you have sufficiently many samples, then it is true even mod $q$ that the pair $(A,b)$ determines $s$ uniquely in an information-theoretic sense. We just don't know any efficient algorithm to carry out the recovery (and known results on the hardness of LWE suggest that it would be extremely surprising if such an algorithm existed at all).

Answer 2

Maybe the reason is: it is impossbile to sample uniformly in \mathbb{Z}. Then b = As + e somehow concentrates. By comparison, sampling A in \mathbb{Z_q} makes b random in $\mathbb{Z}_q$.