Lattice problem

In the following computational problems on lattices are described. These problems are essential for lattice based cryptosystems.

The Shortest Vector Problem (SVP)

In SVP, a basis B of a lattice L is given and one must find the shortest non-zero vector in lattice L. In a approximation version, one must find a a non-zero lattice vector of length at most $\gamma$ len(shortest vector).

The Closest Vector Problem (CVP)

In CVP, a basis B of a lattice L and a vector v not necessarily in the lattice. One must find the lattice vector in L closest to v. In the $gamma$-approximation version one must find a lattice vector at distane at most $\gamma$dist(v, L).

Shortest Independent Vector Problem (SIVP)

Given a lattice L with dimension n, find n linear independent vectors $v_{1},v_{2},...,v_{n}$ of length max ||$v_{i}$|| ≤ $\gamma \lambda _{n}(L)$

Bibliography

• Daniele Micciancio: The Shortest Vector Problem is {NP}-hard to approximate to within some constant. SIAM Journal on Computing. 2001,