Lattice problems

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).

hortest 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,

The_SVP_by_exampleImage:Cvp3.png‎|The_CVP_by_example