Hard lattice problems

Introduction

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 shortest vector problem or the closest 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!

Shortest vector problem + GapSVP

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

Let:

• Lattice

• the basis of the lattice

• the dimension of the lattice

Distance function

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

We will denote the length of the shortest vector with and the length of the next independent vectors in order with

Shortest vector problem

Given a lattice and an arbitrary basis for it our task is to find the shortest vector .

Approximate SVP

We relax the SVP problem a bit. Given an arbitrary basis find a shortest nonzero lattice vector such that . Here is some approximation factor.

Decision SVP (GapSVP)

Given a lattice with a basis we must distinguish if or

Sage example

Closest Vector problem + GapCVP

Closest vector problem

Given a lattice with an arbitrary basis and a vector find the closest lattice vector to

Approximate CVP

Given a lattice with an arbitrary basis and a vector find the closest lattice vector to

Decision CVP (GapCVP)

Given a lattice with a basis and a vector we must decide if

• There exists s.t

Sage example

Bounded distance decoding

Given a lattice with an arbitrary basis , a vector and a real number find a lattice vector s.t

Remark

• If we have the solution to the BDD problem is guaranteed to be unique.

Shortest independent vectors (SIVP)

Given a full rank lattice with an arbitrary basis find linearly independent lattice vectors of length at most or for the approximate version.

Hardness of lattice problems

Resources

• Pictures taken from and "Cryptography made simple - Nigel Smart" and edited a bit

• Or generated by me