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 construction of secure lattice-based cryptosystems. For applications in such cryptosystems, lattices over vector spaces (often Q n {displaystyle mathbb {Q} ^{n}} ) or free modules (often Z n {displaystyle mathbb {Z} ^{n}} ) are generally considered. 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 construction of secure lattice-based cryptosystems. For applications in such cryptosystems, lattices over vector spaces (often Q n {displaystyle mathbb {Q} ^{n}} ) or free modules (often Z n {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 L2. However, other norms (such as Lp) are also considered and show up in a variety of results. Let λ ( L ) {displaystyle lambda (L)} denote the length of the shortest non-zero vector in the lattice L, that is, In SVP, a basis of a vector space V and a norm N (often L2) are given for a lattice L and one must find the shortest non-zero vector in V, as measured by N, in L. In other words, the algorithm should output a non-zero vector v such that N ( v ) = λ ( L ) {displaystyle N(v)=lambda (L)} . In the γ-approximation version SVPγ, one must find a non-zero lattice vector of length at most γ ⋅ λ ( L ) {displaystyle gamma cdot lambda (L)} for given γ ≥ 1 {displaystyle gamma geq 1} . The exact version of the problem is only known to be NP-hard for randomized reductions. By contrast, the corresponding problem with respect to the uniform norm is known to be NP-hard. To solve the exact version of SVP under the Euclidean norm, several different approaches are known, which can be split into two classes: algorithms requiring superexponential time ( 2 ω ( n ) {displaystyle 2^{omega (n)}} ) and poly ⁡ ( n ) {displaystyle operatorname {poly} (n)} memory, and algorithms requiring both exponential time and space ( 2 Θ ( n ) {displaystyle 2^{Theta (n)}} ) in the lattice dimension. The former class of algorithms most notably includes lattice enumeration and random sampling reduction, while the latter includes lattice sieving, computing the Voronoi cell of the lattice, and discrete Gaussian sampling. An open problem is whether algorithms for solving exact SVP exist running in single exponential time ( 2 O ( n ) {displaystyle 2^{O(n)}} ) and requiring memory scaling polynomially in the lattice dimension. To solve the γ-approximation version SVPγ for γ > 1 {displaystyle gamma >1} for the Euclidean norm, the best known approaches are based on using lattice basis reduction. For large γ = 2 Ω ( n ) {displaystyle gamma =2^{Omega (n)}} , the Lenstra–Lenstra–Lovász (LLL) algorithm can find a solution in time polynomial in the lattice dimension. For smaller values γ {displaystyle gamma } , the Block Korkine-Zolotarev algorithm (BKZ) is commonly used, where the input to the algorithm (the blocksize β {displaystyle eta } ) determines the time complexity and output quality: for large approximation factors γ {displaystyle gamma } , a small block size β {displaystyle eta } suffices, and the algorithm terminates quickly. For small γ {displaystyle gamma } , larger β {displaystyle eta } are needed to find sufficiently short lattice vectors, and the algorithm takes longer to find a solution. The BKZ algorithm internally uses an exact SVP algorithm as a subroutine (running in lattices of dimension at most β {displaystyle eta } ), and its overall complexity is closely related to the costs of these SVP calls in dimension β {displaystyle eta } . The problem GapSVPβ consists of distinguishing between the instances of SVP in which the length of the shortest vector is at most 1 {displaystyle 1} or larger than β {displaystyle eta } , where β {displaystyle eta } can be a fixed function of the dimension of the lattice n {displaystyle n} . Given a basis for the lattice, the algorithm must decide whether λ ( L ) ≤ 1 {displaystyle lambda (L)leq 1} or λ ( L ) > β {displaystyle lambda (L)>eta } . Like other promise problems, the algorithm is allowed to err on all other cases.