Lattice problem

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers. For applications in such cryptosystems, lattices over vector spaces (often ${\displaystyle \mathbb {Q} ^{n}}$) or free modules (often ${\displaystyle \mathbb {Z} ^{n}}$) are generally considered.

For all the problems below, assume that we are given (in addition to other more specific inputs) a basis for the vector space V and a norm N. The norm usually considered is the Euclidean norm L². However, other norms (such as L^p) are also considered and show up in a variety of results.^[1]

Throughout this article, let ${\displaystyle \lambda (L)}$ denote the length of the shortest non-zero vector in the lattice L: that is,

${\displaystyle \lambda (L)=\min _{v\in L\smallsetminus \{\mathbf {0} \}}\|v\|_{N}.}$