This section is not complete. Help is needed with relevance + examples in cryptography, algorithms + hardness, relations between problems.

Also needs review from more experienced people.

Now that we are comfortable with lattices we shall study why are they important to cryptography.

Like we said, when we construct cryptosystems we usually are looking for hard problems to base them on. The lattice world provides us with such problems such as the s**hortest vector problem** or the c**losest vector problem.**

What makes lattices even more special is that some cryptographic problems (which we will study in the next chapter) can be reduced to *worst-case *lattice problems which makes them crazy secure. Moreover, some problems are even secure against quantum computers.

But enough talk, let's get right into it!

Before we go into any problems we must first define the concept of distance in a lattice.

Let:

$L=$ Lattice

$\mathcal B =$ the basis of the lattice

$n =$the dimension of the lattice

**Distance function**

Given some distance function (Example: Euclidean norm) the distance from a vector $t$ to the lattice $L$ is the distance from the vector to the closest point in the in lattice.

$\mu(t, L) = \underset{v \in \mathcal{L}}{\min}{\|t-v\|}$

We will denote the length of the shortest vector with $\|v\| = \lambda_1(L)$and the length of the next **independent** vectors in order with $\lambda_i(L) \Rightarrow\lambda_1({L}) \leq \lambda_2({L}) \leq ... \leq \lambda_n({L})$

Given a lattice $L$ and an arbitrary basis $\mathcal{B}$ for it our task is to find the shortest vector $v \in L$.

**Approximate SVP**

We relax the SVP problem a bit. Given an arbitrary basis $\mathcal{B}$find a shortest nonzero lattice vector $v \in L$such that $v < \gamma(n)\cdot \lambda_1(L)$. Here $\gamma(n) > 1$is some approximation factor.

Given a lattice $L$with a basis $\mathcal B$ we must distinguish if $\lambda_1(L) \leq 1$ or $\lambda > \gamma(n)$

# We can find the shortest vector using the LLL algorithmM = matrix([[-1, 2], [-2, 3]])B = M.LLL()print(B[0])# (0, -1)# Or we can use the Integer Lattice classL = IntegerLattice(M)L.shortest_vector()# (-1, 0)

**Closest vector problem**

Given a lattice $L$ with an arbitrary basis $\mathcal B$ and a vector $w \in \mathbb{R}^n$ find the closest lattice vector to $w$ $v \in {L}, \|v-w\| \leq \mu$

**Approximate CVP**

Given a lattice $L$ with an arbitrary basis $\mathcal B$ and a vector $w \in \mathbb{R}^n$ find the closest lattice vector to $w$ $v \in {L}, \|v-w\| < \gamma(n) \cdot \mu$

Given a lattice $L$with a basis $\mathcal B$ and a vector $w$ we must decide if

There exists $v \in L$s.t $\| v - w\| \leq 1$

$\forall v \in L: \|v - w\| > \gamma(n)$

M = matrix([[-1, 2], [-2, 3]])L = IntegerLattice(M)w = vector([1.8, 1.5])L.closest_vector(w)# (2.00000000000000, 2.00000000000000)

Given a lattice $L$ with an arbitrary basis $B$, a vector $w \in \mathbb{R}^n$ and a real number $d \in \mathbb{R}$ find a lattice vector $v \in {L}$ s.t $\|w-v\| < d \cdot \lambda_1({L})$

**Remark**

If we have $d < \dfrac 12$ the solution to the BDD problem is guaranteed to be unique.

Given a full rank lattice $L$ with an arbitrary basis $\mathcal B$find $n$ **linearly independent** lattice vectors of length at most $\lambda_n(L) \Rightarrow \max_i\|v_i\| \leq \lambda_n(L)$ or $\max_i|v_i| \leq \gamma(n) \lambda_n(L)$for the approximate version.

Pictures taken from https://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf and "Cryptography made simple - Nigel Smart" and edited a bit

Or generated by me