Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Chapter 14 Inapproximability Results for Computational Problems on Lattices

Subhash Khot

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

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).

Related papers

On the Limits of Nonapproximability of Lattice Problems

Oded Goldreich, Shafi Goldwasser

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.

Journal of Computer and System Sciences•Jan 1, 1998•231 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

Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm.

Wenbin Chen, Jiangtao Meng

We show that the Closest Vector Problem with Preprocessing over `∞ norm (CVPP∞) is NP-hard to approximate to within a factor of (log n)1/2− , unless NP⊆ DTIME (2polylog(n)). The result is the same as that in [19] by Regev and Rosen, but our proof methods are different from theirs. Their reductions are based on norm embeddings. However, our reductions are based on the reduction of [2] and the property of Hadamard matrix.

Electronic colloquium on computational complexity•Jan 1, 2006•0 citations

ANNEALING-BASED ALGORITHM FOR SOLVING CVP AND SVP

Junpei Yamaguchi, Toshiya Shimizu, Kazuyoshi Furukawa +6 more

Inspired by quantum annealing, digital annealing computers specified for annealing computations have been realized on a large scale, such as the Digital Annealer (DA) developed by Fujitsu and the CMOS Annealing Machine developed by Hitachi. With the progress achieved using these computers, it has become necessary to estimate the computational hardness of cryptographic problems. This paper focuses on lattice problems, such as the closest vector problem (CVP) and shortest vector problem (SVP), which are a class of optimization problems. These problems form the basis of the security of lattice-based cryptography, which is a prime candidate for the NIST post-quantum cryptography standardization. For these lattice problems, we propose methods for generating an Ising model and solving the Ising model on annealing computers with a bit representation as the input, which represents encodings to map each integer variable in the SVP into binary variables. We propose two methods for SVPs, a basic method and a variant incorporating approximately the concept of the classical lattice enumeration. In our experimental results obtained using the second-generation DA, we succeeded in finding a shortest nonzero lattice vector in 40- and 45-dimensional lattices in the Darmstadt SVP Challenge. The basic method with a hybrid bit representation was the fastest among our methods with a bit representation, and the expected running time was estimated as 664 and 13,750 seconds for the 40- and 45-dimensional lattices, respectively. These results provide a benchmark for solving the SVP with annealing computers.

Journal of the Operations Research Society of Japan•Jul 12, 2022•1 citation

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

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
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).
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.
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.
Inspired by quantum annealing, digital annealing computers specified for annealing computations have been realized on a large scale, such as the Digital Annealer (DA) developed by Fujitsu and the CMOS Annealing Machine developed by Hitachi. With the progress achieved using these computers, it has become necessary to estimate the computational hardness of cryptographic problems. This paper focuses on lattice problems, such as the closest vector problem (CVP) and shortest vector problem (SVP), which are a class of optimization problems. These problems form the basis of the security of lattice-based cryptography, which is a prime candidate for the NIST post-quantum cryptography standardization. For these lattice problems, we propose methods for generating an Ising model and solving the Ising model on annealing computers with a bit representation as the input, which represents encodings to map each integer variable in the SVP into binary variables. We propose two methods for SVPs, a basic method and a variant incorporating approximately the concept of the classical lattice enumeration. In our experimental results obtained using the second-generation DA, we succeeded in finding a shortest nonzero lattice vector in 40- and 45-dimensional lattices in the Darmstadt SVP Challenge. The basic method with a hybrid bit representation was the fastest among our methods with a bit representation, and the expected running time was estimated as 664 and 13,750 seconds for the 40- and 45-dimensional lattices, respectively. These results provide a benchmark for solving the SVP with annealing computers.
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-ϵ .
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.