Lattice problem: Difference between revisions

Revision as of 07:02, 15 April 2020

Revision as of 10:45, 28 July 2020

Line 1:

In [[computer science]], '''lattice problems''' are a class of [[Mathematical optimization|optimization]] problems related to mathematical objects called [[Lattice (group)|lattices]]. The conjectured intractability of such problems is central to the construction of secure [[Lattice-based cryptography|lattice-based cryptosystems]]: Lattice problems are an example of [[NP-hardness|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 spacesspace]] (often <math>\mathbb{Q}^n</math>) or [[free module|free modules]] (often <math>\mathbb{Z}^n</math>) are generally considered.

For all the problems below, assume that we are given (in addition to other more specific inputs) a [[Basis (linear algebra)|basis]] for the vector space ''V'' and a [[Norm (mathematics)|norm]] ''N''. The norm usually considered is the Euclidean norm [[Norm (mathematics)#Euclidean norm|''L''²]]. However, other norms (such as [[Norm (mathematics)#p-norm|''L''^p]]) are also considered and show up in a variety of results.<ref>{{cite journal |authorlink=Subhash Khot |first=Subhash |last=Khot |title=Hardness of approximating the shortest vector problem in lattices |journal=J. ACM |volume=52 |issue=5 |year=2005 |pages=789–808 |doi=10.1145/1089023.1089027 }}</ref> Let <math>\lambda(L)</math> denote the length of the shortest non-zero vector in the lattice ''L'', that is,