CryptoBook
Search…
Hard lattice problems
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.

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:
    L=L=
    Lattice
    B=\mathcal B =
    the basis of the lattice
    n=n =
    the dimension of the lattice
Distance function
Given some distance function (Example: Euclidean norm) the distance from a vector
tt
to the lattice
LL
is the distance from the vector to the closest point in the in lattice.
μ(t,L)=minvLtv\mu(t, L) = \underset{v \in \mathcal{L}}{\min}{\|t-v\|}
We will denote the length of the shortest vector with
v=λ1(L)\|v\| = \lambda_1(L)
and the length of the next independent vectors in order with
λi(L)λ1(L)λ2(L)...λn(L)\lambda_i(L) \Rightarrow\lambda_1({L}) \leq \lambda_2({L}) \leq ... \leq \lambda_n({L})

Shortest vector problem

Given a lattice
LL
and an arbitrary basis
B\mathcal{B}
for it our task is to find the shortest vector
vLv \in L
.
Approximate SVP
We relax the SVP problem a bit. Given an arbitrary basis
B\mathcal{B}
find a shortest nonzero lattice vector
vLv \in L
such that
v<γ(n)λ1(L)v < \gamma(n)\cdot \lambda_1(L)
. Here
γ(n)>1\gamma(n) > 1
is some approximation factor.

Decision SVP (GapSVP)

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

Sage example

1
# We can find the shortest vector using the LLL algorithm
2
M = matrix([[-1, 2], [-2, 3]])
3
B = M.LLL()
4
print(B[0])
5
# (0, -1)
6
7
# Or we can use the Integer Lattice class
8
L = IntegerLattice(M)
9
L.shortest_vector()
10
# (-1, 0)
Copied!

Closest Vector problem + GapCVP

Closest vector problem
Given a lattice
LL
with an arbitrary basis
B\mathcal B
and a vector
wRnw \in \mathbb{R}^n
find the closest lattice vector to
ww
vL,vwμv \in {L}, \|v-w\| \leq \mu
Approximate CVP
Given a lattice
LL
with an arbitrary basis
B\mathcal B
and a vector
wRnw \in \mathbb{R}^n
find the closest lattice vector to
ww
vL,vw<γ(n)μv \in {L}, \|v-w\| < \gamma(n) \cdot \mu

Decision CVP (GapCVP)

Given a lattice
LL
with a basis
B\mathcal B
and a vector
ww
we must decide if
    There exists
    vLv \in L
    s.t
    vw1\| v - w\| \leq 1
    vL:vw>γ(n)\forall v \in L: \|v - w\| > \gamma(n)

Sage example

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

Bounded distance decoding

Given a lattice
LL
with an arbitrary basis
BB
, a vector
wRnw \in \mathbb{R}^n
and a real number
dRd \in \mathbb{R}
find a lattice vector
vLv \in {L}
s.t
wv<dλ1(L)\|w-v\| < d \cdot \lambda_1({L})
Remark
    If we have
    d<12d < \dfrac 12
    the solution to the BDD problem is guaranteed to be unique.

Shortest independent vectors (SIVP)

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

Hardness of lattice problems

Resources

Last modified 5mo ago