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.


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.