A lattice $L$ is a vector space similar to a span of vectors, but it can only take integer combinations:
$$ \{a_0v_0 + a_1v_1 + \dots + a_nv_n : a_0,a_1,\dots,a_n \in \Z\} $$
The vectors $v_0,v_1,\dots,v_n$ are the basis $B$. As with regular spans, there can be multiple sets of basis vectors.
A basis is orthogonal if all of the basis vectors are orthogonal to one another, i.e. the dot product $v_i \cdot v_j = 0$ for all $v_i, v_j \in B$.
<aside> ❗ Note that the basis of a lattice is usually written as a matrix, much like with regular vector spaces. It is, however, traditional to put the rows of a lattice as the basis vectors, rather than the columns.
</aside>
Lattice reduction involves finding a basis for the lattice that is more orthogonal than the original basis. It is practically not possible to guarantee finding a perfectly orthogonal basis.
Will get to this at some point, but the important stuff is Gram-Schmidt Orthogonalisation, Gaussian Reduction and LLL (Lenstra-Lenstra-Lovasz).
The Shortest Vector Problem (SVP) involves finding the vector in the lattice $L$ that is closest to the origin.
The Closest Vector Problem (CVP) involves finding the lattice point closest to a given vector.
[Graphic - image from above, but additional non-lattice point as visualisation]
The Shortest Vector Problem is the task of finding the shortest vector in the lattice, i.e. the position vector nearest to the origin that isn’t the origin itself. Lattice reduction is a constant process of finding shorter and more orthogonal basis vectors, so naturally reducing the lattice comes in handy for finding these short vectors.
In fact, in an orthogonal basis, the shortest vector solves the SVP. This is because if you visualise each basis as pointing in a “direction” that is at right angles to every other, every basis vector is uniquely responsible for adding on its own direction.
For example, let’s take the basis $B = \{\begin{pmatrix}1\\ 1\end{pmatrix}, \begin{pmatrix}-2\\ 2\end{pmatrix}\}$. The lattice $L$ looks like this:
[Graphic - the lattice formed by $B$]
If a position vector wants to move in the bottom-left to top-right dimension, only one vector affects this - the basis vector $\begin{pmatrix}1\\ 1\end{pmatrix}$. No additions of $\begin{pmatrix}-2\\ 2\end{pmatrix}$ will ever change it’s position relative to that dimension, because any applications of the other basis vector will always be in a direction at right angles to it.