What are lattices?

Do all the cool post-quantum cryptographers around you talk about lattices and all you can think about is a good salad?

Don't worry! You can be part of the hip crowd at the next cocktail party in just three easy steps!
 

First, I will tell you what a lattice is. It is actually really easy.
Second, we will prove a tiny fact about lattices so that those poor neurons that did all the work in the first step have some friends.
Third, nothing. There isn't even a third step. That's how easy it is!

So, let's tackle the first step. What, actually, is a lattice?
The answer could not be easier. It is simply a grid of points. Like this:

Easy, right?
The formal definition is just as simple:

Given $n$ linearly independent vectors $b_1, b_2, \ldots, b_n \in \mathbb{R}^m$, the lattice generated by them is defined as
\[
\mathcal{L}(b_1, b_2, \ldots, b_n) = \left\{ \sum x_i b_i \middle| x_i \in \mathbb{Z} \right\}.
\]

We can add those so called basis vectors $b_i$ to our diagram and will readily see how each point is constructed.

And now you already know what a lattice is! In the next step we will talk about some more definitions and show the proof of a theorem.

We will be discussing something related to the question of what the length of the shortest non-zero vector in a given lattice $\mathcal{L}$ is.

Definition:

$\lambda_1(\mathcal{L})$ is the length of the shortest non-zero vector in $\mathcal{L}$. We use the euclidean norm for the definition of length.

And we also need the volume of a lattice which we are not going to define formally we will just take it to be the volume of that $n$ dimensional parallelogram in the picture:

Now we can already prove Blichfeld's Theorem! It makes a statement about where we can find a lattice point and roughly goes as follows:

For a lattice $\mathcal{L}\subseteq \mathbb{R}^n$ and a set $S \subseteq \mathbb{R}^n$ where the volume of $S$ is bigger than the volume of the lattice there exist two nonequal points $z_1, z_2 \in S$ such that $z_1 - z_2 \in \mathcal{L}$.

And here is the idea of the proof in a graphical way! First we simply draw an example for the set $S$ in blue:

Now we cut up our set and move all the parts into our first parallelogram!

As you can see there is quite a bit of overlap and the fact that the full volume of the set is bigger than the volume of the lattice aka the parallelogram guarantees there will be at least some overlap somewhere. But if there is overlap then we have two points, that have been moved by multiples of the base vectors and which are now at the same position!

And therefore their difference must be a multiple of base vectors as well and we have found a difference which is a lattice point! Hooray!

Now we will use a little trick to expand this result and make a statement about an actual point from the set being on the lattice not just the difference of two points!

What we will show is called Minkowski's Convex Body Theorem and it states roughly

Let $\mathcal{L}$ be a lattice. Then any centrally-symmetric convex set $S$, with volume bigger than $2^n$ times the volume of the lattice contains a nonzero lattice point.

So after this we will know such a set it will contain a lattice point and using a simple sphere as the set allows us to put a bound on $\lambda_1(\mathcal{L})$.

Let's get to it then!
First we blow up our lattice to twice its size along every dimension!

Now we add our centrally-symmetric convex set $S$. Again in blue.
 

And because we picked the volume of $S$ to be bigger than $2^n$ times the volume of the lattice we still get the colliding points from the last theorem EVEN in the double size lattice!

But since our set $S$ is symmetric about the origin if $z_2 \in S$ it follows that $-z_2 \in S$ and because it is convex $z_1, -z_2 \in S$ implies $\frac{z_1 - z_2}{2} \in S$. And because we've double the size of the lattice and $z_1 - z_2$ is on the bigger lattice it follows that $\frac{z_1 - z_2}{2} \in \mathcal{L}$ and we have shown that a point in our set is also in the lattice.

You can see it quite clearly in the next picture.

As already stated above if we use a simple sphere for this set we can give a bound on $\lambda_1(\mathcal{L})$ based on the volume of $\mathcal{L}$. It is known as Minkowski's First Theorem and states:

 \[
\lambda_1(\mathcal{L}) \leq \sqrt{n}(vol(\mathcal{L})^{1/n}.
\]

Isn't that great?!

If you have now completely fallen in love with lattices but would appreciate real math instead of pictures, worry not!
You will find steps 3 - 14 on Oded Regev's course website! Enjoy!

And in case you accidentally run into him at a conference here is the picture from his website so you don't miss the opportunity to say hello.