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

arXiv:1806.04087 · Theory of Computing

Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors

Ishay Haviv, Oded Regev

Published Jan 1, 2012• 48 citations
arXivHTMLPDF

Abstract

$ \newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RP}{\mathsf{RP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\poly}{\mathop{\mathrm{poly}}} \newcommand{\eps}{\varepsilon} $ We show that unless $\NP \subseteq \RTIME (2^{\poly(\log{n})})$, there is no polynomial-time algorithm approximating the Shortest Vector Problem ($\SVP$) on $n$-dimensional lattices in the $\ell_p$ norm ($1 \leq p<\infty$) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps >0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption $\NP \nsubseteq \RSUBEXP$, we obtain a hardness factor of $n^{c/\log\log{n}}$ for some $c>0$. Our proof starts with Khot's $\SVP$ instances that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novel part is in the analysis, where we show that the lattices of Khot behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.

DOI
10.4086/toc.2012.v008a023

Related papers

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

Ishay Haviv, Oded Regev

We show that unless NP ⊆ RTIME (2poly(log n)), for any ε > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n-dimensional lattices inthe lp norm (1 ≤q p<∞) to within a factor of 2(log n)1-ε. This improves the previous best factor of 2(logn)1/2-ε under the same complexity assumption due to Khot. Under the stronger assumption NP ࣰ RSUBEXP, we obtain a hardness factor of nc/log log n for some c > 0.

ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•84 citations

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

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$

Isaac M. Hair, Amit Sahai

We prove that SVP$_p$ is NP-hard to approximate within a factor of $2^{\log^{1 - \varepsilon} n}$, for all constants $\varepsilon > 0$ and $p > 2$, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVP$_p$ is NP-hard in a finite $\ell_p$ norm. Hardness for SVP$_p$ with $p$ finite was previously only known if NP $\not \subseteq$ RP, and under that assumption, hardness of approximation was only known for all constant factors. As a corollary to our main theorem, we show that under the Sliding Scale Conjecture, SVP$_p$ is NP-hard to approximate within a small polynomial factor, for all constants $p > 2$. Our proof techniques are surprisingly elementary; we reduce from a \emph{regularized} PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.

arXiv:2511.04125•Nov 6, 2025•0 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

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

Lattice Problems: New Lower and Upper Bounds

Yi Tang

In the upcoming era of quantum computation, those successful classical, number-theoretical public-key cryptosystems that get widely deployed nowadays, such as RSA or ElGamal, all face severe insecurity if the adversary gets access to quantum computers. More urgently, time-insensitive secrets on today’s systems are facing immediate threats of the same level due to the “harvest now, decrypt later” attack. The field of post-quantum cryptography aims at building quantum-safe systems to prepare for the future. Among all candidate post-quantum proposals, lattice-based cryptography, which builds cryptosystems based on lattice problems, so far provides the best results in terms of performance, simplicity, and versatility. It is thus important to better understand the complexity of lattice problems. In this thesis, we study a couple of new lower and upper bounds for various lattice problems under various complexity notions. These new results include: 1. (Fine-grained hardness/lower bounds.) The fine-grained (exponential-time) complexity studies the precise constant c in the 2^{n^c} or 2^{c·n} running time for solving a computational problem, usually based on (variants of) the exponential time hypothesis (ETH) or the strong exponential time hypothesis (SETH). Under this complexity notion, for the bounded distance decoding problem (BDD), we give quantitatively improved bounds on the approximation factor α for which BDD_α cannot be solved in 2^{o(n)} or 2^{c·n} time, assuming variants of ETH or SETH, respectively, and for part of our results also assuming a geometric conjecture known as exponential lattice kissing number. For the shortest vector problem (SVP), we show a qualitatively improved result that for some constant approximation factor γ>1, SVP_γ cannot be solved in 2^{c·n} time, assuming a variant of SETH; previously, only analogous result for non-approximate, exact SVP was known. 2. (“Standard” NP-hardness.) The NP-hardness is a classical flag for identifying a computational problem as being hard. For SVP, previously only NP-hardness results under randomized reductions are known (except in corner cases), and whether SVP is “standardly” NP-hard under deterministic reductions is a notoriously longstanding open problem. We propose conjectures about ways to derandomize existing reductions, which would lead to the “standard” NP-hardness of approximate SVP. We also present empirical evidences that support the conjectures. 3. (Parallel algorithms/upper bounds.) The parallel complexity/sequentiality of a computational problem is crucial for its applications in time-release/timed cryptography. We show logarithmic-depth parallel algorithms for a sequential version of the short integer solution problem (SIS), which is used in a certain proof of sequential work (PoSW) timed-cryptographic protocol. This means that sequential SIS has low parallel complexity, as opposed to its previous conjecture. Moreover, we show a polylogarithmic-depth parallel attack that (almost) breaks that PoSW protocol.

•Jan 1, 2025•0 citations
\newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RP}{\mathsf{RP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\poly}{\mathop{\mathrm{poly}}} \newcommand{\eps}{\varepsilon} We show that unless \NP⊆\RTIME(2\poly(log⁡n))\NP \subseteq \RTIME (2^{\poly(\log{n})})\NP⊆\RTIME(2\poly(logn)), there is no polynomial-time algorithm approximating the Shortest Vector Problem (\SVP\SVP\SVP) on nnn-dimensional lattices in the ℓp\ell_pℓp​ norm (1≤p<∞1 \leq p<\infty1≤p<∞) to within a factor of 2(log⁡n)1−\eps2^{(\log{n})^{1-\eps}}2(logn)1−\eps for any \eps>0\eps >0\eps>0. This improves the previous best factor of 2(log⁡n)1/2−\eps2^{(\log{n})^{1/2-\eps}}2(logn)1/2−\eps under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption \NP⊈\RSUBEXP\NP \nsubseteq \RSUBEXP\NP⊈\RSUBEXP, we obtain a hardness factor of nc/log⁡log⁡nn^{c/\log\log{n}}nc/loglogn for some c>0c>0c>0. Our proof starts with Khot's \SVP\SVP\SVP instances that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novel part is in the analysis, where we show that the lattices of Khot behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.
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-ϵ .
SVPp_pp​ is Deterministically NP-Hard for all p>2p > 2p>2, Even to Approximate Within a Factor of 2log⁡1−εn2^{\log^{1-\varepsilon} n}2log1−εn
We prove that SVPp_pp​ is NP-hard to approximate within a factor of 2log⁡1−εn2^{\log^{1 - \varepsilon} n}2log1−εn, for all constants ε>0\varepsilon > 0ε>0 and p>2p > 2p>2, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVPp_pp​ is NP-hard in a finite ℓp\ell_pℓp​ norm. Hardness for SVPp_pp​ with ppp finite was previously only known if NP ⊈\not \subseteq⊆ RP, and under that assumption, hardness of approximation was only known for all constant factors. As a corollary to our main theorem, we show that under the Sliding Scale Conjecture, SVPp_pp​ is NP-hard to approximate within a small polynomial factor, for all constants p>2p > 2p>2. Our proof techniques are surprisingly elementary; we reduce from a \emph{regularized} PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.
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.>
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.
In the upcoming era of quantum computation, those successful classical, number-theoretical public-key cryptosystems that get widely deployed nowadays, such as RSA or ElGamal, all face severe insecurity if the adversary gets access to quantum computers. More urgently, time-insensitive secrets on today’s systems are facing immediate threats of the same level due to the “harvest now, decrypt later” attack. The field of post-quantum cryptography aims at building quantum-safe systems to prepare for the future. Among all candidate post-quantum proposals, lattice-based cryptography, which builds cryptosystems based on lattice problems, so far provides the best results in terms of performance, simplicity, and versatility. It is thus important to better understand the complexity of lattice problems. In this thesis, we study a couple of new lower and upper bounds for various lattice problems under various complexity notions. These new results include: 1. (Fine-grained hardness/lower bounds.) The fine-grained (exponential-time) complexity studies the precise constant c in the 2^{n^c} or 2^{c·n} running time for solving a computational problem, usually based on (variants of) the exponential time hypothesis (ETH) or the strong exponential time hypothesis (SETH). Under this complexity notion, for the bounded distance decoding problem (BDD), we give quantitatively improved bounds on the approximation factor α for which BDD_α cannot be solved in 2^{o(n)} or 2^{c·n} time, assuming variants of ETH or SETH, respectively, and for part of our results also assuming a geometric conjecture known as exponential lattice kissing number. For the shortest vector problem (SVP), we show a qualitatively improved result that for some constant approximation factor γ>1, SVP_γ cannot be solved in 2^{c·n} time, assuming a variant of SETH; previously, only analogous result for non-approximate, exact SVP was known. 2. (“Standard” NP-hardness.) The NP-hardness is a classical flag for identifying a computational problem as being hard. For SVP, previously only NP-hardness results under randomized reductions are known (except in corner cases), and whether SVP is “standardly” NP-hard under deterministic reductions is a notoriously longstanding open problem. We propose conjectures about ways to derandomize existing reductions, which would lead to the “standard” NP-hardness of approximate SVP. We also present empirical evidences that support the conjectures. 3. (Parallel algorithms/upper bounds.) The parallel complexity/sequentiality of a computational problem is crucial for its applications in time-release/timed cryptography. We show logarithmic-depth parallel algorithms for a sequential version of the short integer solution problem (SIS), which is used in a certain proof of sequential work (PoSW) timed-cryptographic protocol. This means that sequential SIS has low parallel complexity, as opposed to its previous conjecture. Moreover, we show a polylogarithmic-depth parallel attack that (almost) breaks that PoSW protocol.