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.

  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 '17 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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