3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think what you are looking for is proved in Brakerski-Langlois-Peikert-Regev-Stehle STOC’13, Section 4.1, “first is errorless LWE.” $\endgroup$
    – Chris Peikert
    Commented Sep 29, 2019 at 13:34
  • $\begingroup$ Sorry, I spent some time to answer, but thanks a lot for the answer! $\endgroup$
    – Léo Colisson
    Commented Mar 27, 2020 at 15:01

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Léo Colisson
    Commented Apr 3, 2019 at 9:56
  • $\begingroup$ @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). $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Apr 3, 2019 at 10:45
  • $\begingroup$ 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... $\endgroup$
    – Léo Colisson
    Commented Apr 3, 2019 at 11:12
  • $\begingroup$ @tobiasBora Oh, Okay, I was thinking of an oracle to the search version of LWE, in this case, the answer could easily be verified. $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Apr 3, 2019 at 11:15
  • 1
    $\begingroup$ 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! $\endgroup$
    – Léo Colisson
    Commented Apr 3, 2019 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.