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?

• I think what you are looking for is proved in Brakerski-Langlois-Peikert-Regev-Stehle STOC’13, Section 4.1, “first is errorless LWE.” Sep 29 '19 at 13:34
• Sorry, I spent some time to answer, but thanks a lot for the answer! Mar 27 '20 at 15:01

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.

• Thanks for the answer. I agree for the first reduction (which is not the one I'm interested in), but I have problems with the second one. Indeed, as an adversary, if I receive an instance of LWE, $(A,b)$, I don't know $s$, so I cannot produce $b_0 := a_0 \cdot s$. Did I miss something? Apr 3 '19 at 9:56
• @tobiasBora Yes, you are right. I am sorry, I wrote it in a hurry. But take a look to the edition I made. I think that depending on the parameters, they should be polynomially equivalent to each other (a polynomial number of call to an oracle of your problem should be sufficient to solve LWE). Apr 3 '19 at 10:45
• Thanks for the edit. I was also thinking to do that, but the problem is that it's not possible to check if the solution you get from the oracle is true or not (the answer is just one bit), so even if the call to the oracle with the good error produces the good answer, the calls to the other oracles may lead to different answers and I don't see how you can choose one oracle. Maybe first call gives 0, second gives 1, third gives 1, fourth gives 0... How do you know which call is the good one? I've the feeling that we need some boosting arguments, but not sure... Apr 3 '19 at 11:12
• @tobiasBora Oh, Okay, I was thinking of an oracle to the search version of LWE, in this case, the answer could easily be verified. Apr 3 '19 at 11:15
• Hum, it may be enough indeed, but I want more something like searchMyLWEproblem <-> decisionMyLWEproblem. I'll try to see if the proof of searchLWE <-> decisionLWE can be mimic, but I guess it makes sense. I'll let you know, thanks for your help! Apr 3 '19 at 11:57