© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Journal of Computer and System Sciences

On the Limits of Nonapproximability of Lattice Problems

Oded Goldreich, Shafi Goldwasser

Published Jan 1, 1998• 231 citations

Abstract

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 vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), Håstad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.

DOI: 10.1006/jcss.1999.1686

Related papers

Hardness of approximating the shortest vector problem in lattices

Subhash Khot

Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓ p norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2 poly (log n ) ), we show that there is no polynomial-time algorithm with approximation ratio 2 (log n ) 1/2−ϵ where n is the dimension of the lattice and ϵ > 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves some constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product , a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2 (log n ) 1/2-ϵ .

Journal of the ACM•Sep 1, 2005•211 citations

Inapproximability of the shortest vector problem: Toward a deterministic reduction

Daniele Micciancio

Abstract: We prove that the Shortest Vector Problem (SVP) on point lattices is NPhard to approximate for any constant factor under polynomial-time randomized reductions with one-sided error that produce no false positives. We also prove inapproximability for quasi-polynomial factors under the same kind of reductions running in subexponential time. Previous hardness results for SVP either incurred two-sided error, or only proved hardness for small constant approximation factors. Close similarities between our reduction and recent results on the complexity of the analogous problem for linear codes make our new proof an attractive target for derandomization, paving the road to a possible NP-hardness proof for SVP under deterministic polynomial-time reductions.

•Oct 9, 2013•2 citations

The hardness of approximate optima in lattices, codes, and systems of linear equations

Sanjeev Arora, László Babai, Jacques Stern +1 more

We prove the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.>

Annual Symposium on Foundations of Computer Science•Dec 30, 2002•181 citations

Chapter 14 Inapproximability Results for Computational Problems on Lattices

Subhash Khot

In this article, we present a survey of known inapproximability results for computational problems on lattices, viz. the Shortest Vector Problem (SVP), the Closest Vector Problem (CVP), the Closest Vector Problem with Preprocessing (CVPP), the Covering Radius Problem (CRP), the Shortest Independent Vectors Problem (SIVP), and the Shortest Basis Problem (SBP).

•Jan 1, 2010•0 citations

Lattice problems in NP ∩ coNP

Dorit Aharonov, Oded Regev

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of √n lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [1993], Goldreich and Goldwasser [2000], and Aharonov and Regev [2003]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier series over the lattice. This technique might be useful elsewhere---we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP) improving on a previous result of Regev[2003]. An interesting fact is that our result emerged from a “dequantization” of our previous quantum result in Aharonov and Regev [2003]. This route to proving purely classical results might be beneficial elsewhere.

Journal of the ACM•Sep 1, 2005•179 citations

Lattice Problems in NP ∩ coNP

Dorit Aharonov, Oded Regev

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 mutually-incomparable previous results regarding these lattice problems: Banaszczyk (1993), Goldreich and Goldwasser (2000), and Aharonov and Regev (2003). Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier transform over the lattice. This technique might be useful elsewhere - we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP,) improving on a previous result of Regev (2003). An interesting fact is that our result emerged from a "dequantization" of our previous quantum result in (Aharanov and Regev, 2003). This route to proving purely classical results might be beneficial elsewhere.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•46 citations

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 vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), Håstad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.

Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓ p norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2 poly (log n ) ), we show that there is no polynomial-time algorithm with approximation ratio 2 (log n ) 1/2−ϵ where n is the dimension of the lattice and ϵ > 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves some constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product , a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2 (log n ) 1/2-ϵ .

Abstract: We prove that the Shortest Vector Problem (SVP) on point lattices is NPhard to approximate for any constant factor under polynomial-time randomized reductions with one-sided error that produce no false positives. We also prove inapproximability for quasi-polynomial factors under the same kind of reductions running in subexponential time. Previous hardness results for SVP either incurred two-sided error, or only proved hardness for small constant approximation factors. Close similarities between our reduction and recent results on the complexity of the analogous problem for linear codes make our new proof an attractive target for derandomization, paving the road to a possible NP-hardness proof for SVP under deterministic polynomial-time reductions.

We prove the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.>

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of √n lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [1993], Goldreich and Goldwasser [2000], and Aharonov and Regev [2003]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier series over the lattice. This technique might be useful elsewhere---we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP) improving on a previous result of Regev[2003]. An interesting fact is that our result emerged from a “dequantization” of our previous quantum result in Aharonov and Regev [2003]. This route to proving purely classical results might be beneficial elsewhere.

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 mutually-incomparable previous results regarding these lattice problems: Banaszczyk (1993), Goldreich and Goldwasser (2000), and Aharonov and Regev (2003). Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier transform over the lattice. This technique might be useful elsewhere - we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP,) improving on a previous result of Regev (2003). An interesting fact is that our result emerged from a "dequantization" of our previous quantum result in (Aharanov and Regev, 2003). This route to proving purely classical results might be beneficial elsewhere.