# Hardness of approximating the shortest vector problem in lattices

@article{Khot2004HardnessOA, title={Hardness of approximating the shortest vector problem in lattices}, author={Subhash Khot}, journal={45th Annual IEEE Symposium on Foundations of Computer Science}, year={2004}, pages={126-135} }

Let p > 1 be any fixed real. We show that assuming NP /spl nsube/ RP, it is hard to approximate the shortest vector problem (SVP) in l/sub p/ norm within an arbitrarily large constant factor. Under the stronger assumption NP /spl nsube/ RTIME(2/sup poly(log n)/), we show that the problem is hard to approximate within factor 2/sup log n1/2 - /spl epsi// where n is the dimension of the lattice and /spl epsi/> 0 is an arbitrarily small constant. This greatly improves all previous results in l/sub… Expand

#### 215 Citations

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

- Mathematics, Computer Science
- STOC '07
- 2007

The main novel part is in the analysis, where it is shown that Khot's lattices behave nicely under tensorization, and a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski is used. Expand

The complexity of the covering radius problem on lattices and codes

- Mathematics, Computer Science
- Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004.
- 2004

The computational complexity of the covering radius problem for point lattices, and approximation versions of the problem for both lattices and linear codes are studied, and it is proved that the problem is NP-hard for every constant approximation factor. Expand

Worst-case to average-case reductions based on Gaussian measures

- Mathematics, Computer Science
- 45th Annual IEEE Symposium on Foundations of Computer Science
- 2004

It is shown that solving modular linear equation on the average is at least as hard as approximating several lattice problems in the worst case within a factor almost linear in the rank of the lattice, and it is proved that the distribution that one obtains after adding Gaussian noise to the lattices has the following interesting property. Expand

Limits on the Hardness of Lattice Problems in ell _p Norms

- Mathematics, Computer Science
- Computational Complexity Conference
- 2007

The main technical contributions are a very general analysis of Gaussian distributions over lattices, which may be of independent interest and analytical techniques of Banaszczyk which, to the authors' knowledge, have yet to be exploited in computer science. Expand

Limits on the Hardness of Lattice Problems in ℓp Norms

- Computer Science, Mathematics
- Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07)
- 2007

The results improve prior approximation factors for ℓp norms by up to up to $$\sqrt{n}$$ factors, and provide some evidence that lattice problems in ™p norms (for p > 2) may not be substantially harder than they are in the ™2 norm. Expand

Worst-Case to Average-Case Reductions Based on Gaussian Measures

- Mathematics, Computer Science
- SIAM J. Comput.
- 2007

It is shown that finding small solutions to random modular linear equations is at least as hard as approximating several lattice problems in the worst case within a factor almost linear in the dimension of the lattice, and it is proved that the distribution that one obtains after adding Gaussian noise to a lattice has the following interesting property. Expand

(Gap/S)ETH hardness of SVP

- Mathematics, Computer Science
- STOC
- 2018

We prove the following quantitative hardness results for the Shortest Vector Problem in the ℓp norm (SVP_p), where n is the rank of the input lattice. For “almost all” p > p0 ≈ 2.1397, there is no… Expand

Lattices that admit logarithmic worst-case to average-case connection factors

- Computer Science, Mathematics
- STOC '07
- 2007

An average-case problem that is as hard as finding γ(n)-approximate shortest nonzero vectors in certain n-dimensional lattices in the worst case is exhibited, and reductions between various worst-case problems on ideal lattices are given, showing for example that the shortest vector problem is no harder than the closest vector problem. Expand

Efficient reductions among lattice problems

- Mathematics, Computer Science
- SODA '08
- 2008

It is shown that for any γ ≥ 1, approximating all thesuccessive minima of a lattice within a factor γ reduces under deterministic polynomial time rank-preserving reductions to approximating the <i>Closest Vector Problem</i> (CVP) within the samefactor γ. Expand

Hardness of the covering radius problem on lattices

- Mathematics, Computer Science
- 21st Annual IEEE Conference on Computational Complexity (CCC'06)
- 2006

It is shown that for any large enough p les infin there exists a constant cp > 1 such that CRP in the lscrp norm is Pi2-hard to approximate to within any constant less than cp. Expand

#### References

SHOWING 1-10 OF 51 REFERENCES

Hardness of approximating the shortest vector problem in high L/sub p/ norms

- Mathematics, Computer Science
- 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
- 2003

For large values of p, this improves the factor 2/sup 1/p/ - /spl delta/ hardness shown by D. Micciancio (1998). Expand

The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)

- Computer Science, Mathematics
- STOC '98
- 1998

There is a prob-abilistic Turing-machine which in polynomial time reduces any problem in NP to instances of the shortest vector problem, provided that it can use an oracle which returns the solution of the longest vector problem if an instance of it is presented (by giving a basis of the corresponding lattice). Expand

The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant

- Mathematics, Computer Science
- SIAM J. Comput.
- 2000

It is shown that approximating the shortest vector problem to within any constant factor less than $\sqrt[p]2$ is hard for NP under reverse unfaithful random reductions with inverse polynomial error probability, and an alternative construction of Ajtai's constructive variant of Sauer's lemma that greatly simplifies AjTai's original proof is given. Expand

Lattice Problems in NP cap coNP

- Mathematics, Computer Science
- FOCS
- 2004

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of /spl radic/n lie in NP intersect coNP. The result (almost) subsumes the three… Expand

On the Limits of Nonapproximability of Lattice Problems

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 2000

We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n, of optimization problems in integer lattices, specifically, the closest… Expand

Generating hard instances of lattice problems (extended abstract)

- Mathematics, Computer Science
- STOC '96
- 1996

We give a random class of lattices in Zn whose elements can be generated together with a short vector in them so that, if there is a probabilistic polynomial time algorithm which finds a short vector… Expand

Lattice problems in NP ∩ coNP

- Mathematics, Computer Science
- JACM
- 2005

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of &nradic; lie in NP intersect coNP. The result (almost) subsumes the three… Expand

Generating Hard Instances of Lattice Problems

- Computer Science
- Electron. Colloquium Comput. Complex.
- 1996

We give a random class of lattices in Z n so that, if there is a probabilistic polynomial time algorithm which nds a short vector in a random lattice with a probability of at least 1 2 then there is… Expand

On the limits of non-approximability of lattice problems

- Computer Science, Mathematics
- STOC '98
- 1998

It is concluded that approximating CVP (resp., SVP) within a factor of fi is in NP n codM, and the closest vector problem (CVP), and the shortest vector pcoblom @VP are shown. Expand

Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors

- Computer Science, Mathematics
- Electron. Colloquium Comput. Complex.
- 1999

This result establishes the widely believed conjecture by which the shortest vector problem is not harder than the closest vector problem, and can be easily adapted to establish an analogous result for the corresponding computational problems for linear codes. Expand