Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity.

LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE is form of

$(\mathbf{A},\mathbf{sA+e}) \approx (\mathbf{A},\mathbf{r}) $

My question is why the random matrix is the form $\mathbf{A} \in \mathbb{Z}_q^{m\times n}$ ($m >> n$)?

Is $m=1$ easily solved?

I think in the case of Ring LWE, $m=1$ can work.

  • $\begingroup$ LWE does not require giving a bunch of samples to the attacker. Rather, LWE (properly parameterized) appears to be hard even if the attacker gets many samples. Giving fewer samples cannot make the problem any easier to break (and may make it harder), because samples can be ignored. Indeed, some applications of LWE give out not that many samples, while others give away many more. $\endgroup$ Sep 23, 2022 at 19:09

2 Answers 2

  1. The number of rows in matrix $\textbf{A}$ shows the number of LWE samples and $m=1$ means the adversary has access only to one sample. This would be a naive adversary model and would not be suitable for assessing the true hardness of the Problem. To consider a more powerful adversary model, a (seemingly) stronger definition is to assume that the adversary has access to arbitrary $m$ independent samples.

  2. In the case of R-LWE, a single sample ($m=1$) takes the place of $n$ (correlated) LWE samples.

    Even if we assume that the adversary has only one sample, then just as in LWE, finding the secret seems (intuitively) to be harder.

  • $\begingroup$ Thank you. Could you elaborate your second answer? In the case of RLEW $n=m$ holds, is it really secure? $\endgroup$
    – mallea
    Aug 15, 2017 at 19:42

There's decision-LWE and there's search-LWE. Decision-LWE can only get harder as the number of samples decreases; if you can distinguish for 1 sample and are given $m$ samples, you can always ignore $m-1$ of them. So $m=1$ is the hardest case possible for decision-LWE. For search-LWE, if the number of samples is too small, e.g. $m=1$, the problem is easy because the number of equations you have to solve is small and there are many solutions. If you just pick a random $s$, you have a success probability of at least $1/q$.

EDIT: see the comment below.

  • 1
    $\begingroup$ The LWE search problem is not easy when $m=1$, it is information-theoretically hard. This is because the problem is to find the secret $s$ that the challenger used to create the samples, not just some $s$ that is consistent with them. With just one sample, almost no information about $s$ is revealed, so it is effectively impossible to guess. $\endgroup$ Sep 23, 2022 at 20:33
  • $\begingroup$ @ChrisPeikert Thanks you that clarification. $\endgroup$
    – Myath
    Sep 23, 2022 at 20:56

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.