Lattice problem
In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes.
In the γ-approximation version SVPγ, one must find a non-zero lattice vector of length at most
[4] To solve the exact version of the SVP under the Euclidean norm, several different approaches are known, which can be split into two classes: algorithms requiring superexponential time (
[15] An open problem is whether algorithms for solving exact SVP exist running in single exponential time (
for the Euclidean norm, the best known approaches are based on using lattice basis reduction.
, the Lenstra–Lenstra–Lovász (LLL) algorithm can find a solution in time polynomial in the lattice dimension.
) determines the time complexity and output quality: for large approximation factors
), and its overall complexity is closely related to the costs of these SVP calls in dimension
The problem GapSVPβ consists of distinguishing between the instances of SVP in which the length of the shortest vector is at most
), the problem is equivalent to GapSVPγ because[20] a preprocessing done using the LLL algorithm makes the second condition (and hence,
[22] Using PCP tools, Arora et al. showed that CVP is hard to approximate within factor
[24] Algorithms for CVP, especially the Fincke and Pohst variant,[6] have been used for data detection in multiple-input multiple-output (MIMO) wireless communication systems (for coded and uncoded signals).
[25][13] In this context it is called sphere decoding due to the radius used internal to many CVP solutions.
[26] It has been applied in the field of the integer ambiguity resolution of carrier-phase GNSS (GPS).
In the same field, the general CVP problem is referred to as Integer Least Squares.
, and the algorithm must answer whether one of the following holds: The opposite condition is that the closest lattice vector is at a distance
Schnorr, in 1987, showed that deterministic polynomial time algorithms can solve the problem for
[28] Ajtai et al. showed that probabilistic algorithms can achieve a slightly better approximation factor of
[31] For lower bounds, Dinur et al. showed in 1998 that the problem is NP-hard for
-approximate version, given a lattice L with dimension n, one must find n linearly independent vectors
Many problems become easier if the input basis consists of short vectors.
The approximation version SBPγ problem consist of finding a basis whose longest vector is at most
Average-case hardness of problems forms a basis for proofs-of-security for most cryptographic schemes.
However, experimental evidence suggests that most NP-hard problems lack this property: they are probably only worst case hard.
Moreover, worst-case hardness of some lattice problems have been used to create secure cryptographic schemes.
The above lattice problems are easy to solve if the algorithm is provided with a "good" basis.
The Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) was an early efficient algorithm for this problem which could output an almost reduced lattice basis in polynomial time.
[33] This algorithm and its further refinements were used to break several cryptographic schemes, establishing its status as a very important tool in cryptanalysis.
The success of LLL on experimental data led to a belief that lattice reduction might be an easy problem in practice; however, this belief was challenged in the late 1990s, when several new results on the hardness of lattice problems were obtained, starting with the result of Ajtai.
[2][3] Building on these results, Ajtai and Dwork created a public-key cryptosystem whose security could be proven using only the worst case hardness of a certain version of SVP,[34] thus making it the first result to have used worst-case hardness to create secure systems.
