LWE secure with one entry without noise I'd like to know, is Learning With Error (LWE) (with modular noise) "secure" if one entry has no noise?

More precisely, I have:


a random matrix $A \in \mathbb{Z}_q^{m \times n}$
a random string $s \in \mathbb{Z_q}^{n\times 1}$
and a "small" noise vector $e \in \mathbb{Z}_q^{m\times1}$, such that the first component of $e$ is $0$, i.e. $e_{1,1} = 0$.


Then, can I distinguish between $(A, As+e)$ and $(A, b)$, with $b \in \mathbb{Z}_q^{m}$ chosen uniformly at random?
Yes. This problem is roughly equivalent to LWE.

If you have an oracle to solve $LWE_{n, q, m, \sigma}$, then you can solve an instance $(A, b := As + e)$ of your problem just by sampling a Gaussian $e_1$ and add it to $b_1$, that is, defining $b' := b + (e_1, 0, 0, ..., 0)$.

Of course, $(A, b')$ is a legitimate instance of $LWE_{n, q, m, \sigma}$ and can be solved with the oracle.

On the other hand, if you have an oracle to your problem, then given an instance $(A, b := As + e)$ of $LWE_{n, q, m, \sigma}$, you can try values to $e_1$ in order to produce a new error vectors with a zero in the first entry.

For typical LWE instances, $q$ is polynomially big in $n$ and the Gaussian parameter $\sigma$ is $\alpha \cdot q$ for some $\alpha$ between zero and one. Therefore, the errors values are also polynomially big in $n$ (they are bounded by $k \cdot \sigma$ for some very small constant $k$ with probability exponentially close to 1).

If you do a loop through those possible values of $e_1$, always defining $b' := b - (e_1, 0, 0, ..., 0)$, at some point, you will subtract the correct value and produce a legitimate instance of your problem, which the oracle will then be able to solve.