I was trying to understand Learning with Errors for Lattice-based Cryptography and I came across this.
The learning with errors problem is: Given an $m \times n$ matrix $A$ and a vector $b \equiv As + e \pmod q$, where $e \in \mathbb{Z}^m_Q$ is a "short" error vector, to compute $s \in \mathbb{Z}^n_q$.
Can somebody explain what does a "short" vector in this context means ?
Short just means small (in terms of some metric, usually Euclidean).
You can see that if $e$ is the zero vector, $s$ becomes trivial to recover, using Gaussian elimination. If $e$ is uniformly random, then you can imagine that it is impossible to recover any information on $s$, since it is hidden against a uniformly random backdrop.
If you're familiar with lattices, it might be helpful to picture the following instead. Consider the LWE lattice
$ \mathcal{L} := \{ \mathbf{A} \mathbf{s} : \mathbf{s} \in \mathbb{Z}^n_q \} + q \mathbb{Z}^m .$
If the vector $e$ is small enough, $b$ is close to only one of the points in this lattice. In other words, the LWE problem becomes a bounded-distance decoding problem on this lattice. If $e$ is too large, $b$ might be closer to another vector in this lattice.
Since we are typically interested in recovering $s$ and not a set of possible secrets, we must be given a guarantee that $e$ is sufficiently short (hence bounded distance decoding).
So "short" just means that $s$ is recoverable. Usually, $e$ is sampled from a discrete distribution approximating a Gaussian centered around 0, with width small relative to $q$. This allows one to ensure that $s$ is recoverable with an arbitrarily high probability, while still making the problem as difficult as possible.
