0
$\begingroup$

One of the various equivalent definitions of the LWE problem is the following:

Let $n,q$ be integers ($q$ usually is a prime number), $\chi$ a discrete probability distribution over $\mathbb{Z}$ (usually a discrete Gaussian distribution) and $s$ a secret vector from $\mathbb{Z}_q^n$.

We denote $\mathcal{L}_{s,\chi}$ the probability distribution over $\mathbb{Z}_q^n \times \mathbb{Z}_q$ obtained by choosing $a \in \mathbb{Z}_q^n$ uniformly at random, choosing $e$ uniformly at random from $\chi$ and considering it in $\mathbb{Z}_q$, and calculating $(a,b=(\langle a,s\rangle + e)) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$.

The Search Learning With Errors is to recover $s$ from samples $(a,b)$ obtained from $\mathcal{L}_{s,\chi}$.

My questions is why do we add the error $e$? I suppose that it is for security reasons. In that case, how we would be able to obtain $s$ from $(a,b=(\langle a,s\rangle))$?

Since adding some error $e$ is a central block in a lot of lattice-based constructions, this could be a more general question. What is the point of adding this error?

$\endgroup$
2
$\begingroup$

In that case, how we would be able to obtain $s$ from $(a,b=(\langle a,s\rangle))$?

The operation $\langle a,s\rangle$ is a matrix multiplication, that is, completely linear, and hence Gaussian elimination allows us to recover $s$ efficiently.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Another reason is indistinguishability. $\endgroup$ – kelalaka Jul 2 at 18:13
  • 1
    $\begingroup$ Can you expand this answer? The value $\langle a,s\rangle$ is just one inner product, so it’s not enough information to recover $s$ uniquely (when $n>1$). We would need many samples (at least $n$) from the distribution to get invertible matrix multiplication. $\endgroup$ – Chris Peikert Jul 3 at 11:22

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.