3
$\begingroup$

I read the statement of the Decision Learning with error problem is:

  • distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e)$ from uniformly random samples.

Can anyone explain what does it mean to distinguish $(\vec a, \langle \vec a, \vec s \rangle + e)$ from random samples? Does it mean subjecting $(\vec a, \langle \vec a, \vec s \rangle + e)$ to some statistical test for randomness? From what I understand a and e are both randomly sampled from a uniform distribution, So why would $\langle \vec a, \vec s \rangle + e$ not look like random data? Is it saying that $\langle \vec a, \vec s \rangle + e$ is a one-way hash function?

$\endgroup$
3
$\begingroup$

As Peikert has commented (and my first answer was not dealing with this issue carefully), the LWE problem asks you to distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e \mod q) \in \mathbb{Z}_q^{n+1}$ and $\vec u \in \mathbb{Z}_q^{n+1}$ (with each entry of $\vec u$ sampled uniformly from $\mathbb{Z}_q$) given many samples.

This is why the LWE problem is usually defined with a parameter $m$, which represents the number of samples $(\vec a_i, \langle \vec a_i, \vec s \rangle + e_i \mod q)$ that you can get. Notice that all the samples use the same fixed secret $\vec s$.

The problem says nothing about how you are going to distinguish those two distributions. Given many samples, if you run an statistical test or some clever algorithm using lattices, it does not matter, as long as you can tell to which distribution those samples belong.

And about $b_i := \langle \vec a_i, \vec s \rangle + e_i \mod q$ being distributed uniformly on $\mathbb{Z}_q$, indeed, if you have a single sample, then that is the case, but again, if you have several samples, say, $m$, then, the distribution of $(a_i, b_i)_{i=1}^m$ can possibly be distinguished from the uniform over $\mathbb{Z}_q^{n+1}$. In particular, if you can recover $\vec s$, then you can simply compute $b_i - \langle \vec a_i, \vec s \rangle \mod q$ to get $e_i$, which are all small, thus, not uniformly distributed.

A final note, in your question you say "From what i understand a and e are both randomly sampled from uniform distribution", but actually, only $\vec a$ is uniformly chosen from $\mathbb{Z}_q$, the noise term $e$ usually follows a distribution that is likely to sample values much smaller than $q$ (like a Gaussian distribution with parameter approx. $\sqrt n$).

$\endgroup$
3
  • $\begingroup$ I think this answer is misleading. Regarding the OP’s final questions, the point is that the attacker is given many samples with independent values of $a,e$ and the same $s$. This is absolutely critical to LWE being nontrivial. A single sample is indeed truly uniformly random, but several samples are not. “If you know $s$ (or can somehow find it)” is not relevant to the question of whether a single sample is uniformly random; it is so. $\endgroup$ Feb 20 '20 at 16:50
  • $\begingroup$ @ChrisPeikert yes, you are right. I indeed said "given many samples" in the second paragraph, but the others (specially the last) can lead to wrong conclusions. I have edited the answer. Thank you for the comment. $\endgroup$ Feb 20 '20 at 17:37
  • 1
    $\begingroup$ Thanks; the answer is very good now. $\endgroup$ Feb 20 '20 at 17:38

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.