- 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
Wikimedia Foundation. 2010.