What is meant by a "short" vector in cryptography? 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.