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

We show that unless NP ⊆ RTIME (2^{poly(log n)}), for any ε > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on <i>n</i>-dimensional lattices inthe l_p 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 n^{c/log log n} for some c > 0. Our proof starts with Khot's SVP instances from that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product oflattices. The main novel part is in the analysis, where we show that Khot's lattices 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.

• Publication year

  2007

• Venue

  Symposium on the Theory of Computing

• Publication date

  2007-06-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1250790.1250859arXiv 1806.04087
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• 1 . 2 Lattice-based cryptography

  2008cited by this paper
• Efficient reductions among lattice problems

  2008cited by this paper
• Approximating the Svp to within a Factor ?

  2007cited by this paper
• Lattice-Based Cryptography

  2006cited by this paper
• Lattice problems and norm embeddings

  2006cited by this paper
• Lattice problems in NP ∩ coNP

  2005cited by this paper
• Hardness of approximating the shortest vector problem in lattices

  2004cited by this paper
• Approximating CVP to Within Almost-Polynomial Factors is NP-Hard

  2003cited by this paper
• Complexity of lattice problems - a cryptographic perspective

  2002cited by this paper
• Complexity of lattice problems

  2002cited by this paper
• Economic inequality and burden-sharing in the provision of local environmental quality

  2002cited by this paper
• A sieve algorithm for the shortest lattice vector problem

  2001cited by this paper
• The Probablistic Method

  2000cited by this paper
• On the Limits of Nonapproximability of Lattice Problems

  2000cited by this paper
• Approximating the SVP to within a Factor (1+1/dimxi) Is NP-Hard under Randomized Reductions

  1999cited by this paper
• Hardness of approximating the minimum distance of a linear code

  1999cited by this paper
• The shortest vector in a lattice is hard to approximate to within some constant

  1998cited by this paper
• The Probabilistic Method

  1998cited by this paper
• The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)

  1998cited by this paper
• Generating hard instances of lattice problems (extended abstract)

  1996cited by this paper
• The hardness of approximate optima in lattices, codes, and systems of linear equations

  1993cited by this paper
• Efficient probabilistically checkable proofs and applications to approximations

  1993cited by this paper
• Eecient Probabilistically Checkable Proofs and Applications to Approximation

  1993cited by this paper
• A course in computational algebraic number theory

  1993cited by this paper
• Minkowski's Convex Body Theorem and Integer Programming

  1987cited by this paper
• A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms

  1987cited by this paper
• On Lovász’ lattice reduction and the nearest lattice point problem

  1986cited by this paper
• Factoring polynomials with rational coefficients

  1982cited by this paper
• Factoring polynomials with rational coeficients

  1982cited by this paper
• Symmetric Bilinear Forms

  1973cited by this paper
• Geometrie der Zahlen

  year unknowncited by this paper

• Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms

  2026cites this paper
• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓp norms for p>2

  2025influential citation
• Worst-case Analysis of Lattice Enumeration Algorithm over Modules

  2025cites this paper
• SVPp is Deterministically NP-Hard for all p > 2, Even to Approximate Within a Factor of 2log1-ε n

  2025influential citation
• Scaling Lattice Sieves across Multiple Machines

  2025cites this paper
• SVPp is NP-Hard for all p > 2, Even to Approximate Within a Factor of 2{log1-ϵ n

  2025influential citation
• Worst-Case to Average-Case Hardness of LWE: An Alternative Perspective

  2024cites this paper
• Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective

  2024cites this paper
• Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH

  2024cites this paper
• On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut

  2024cites this paper
• On the Hardness of Learning One Hidden Layer Neural Networks

  2024cites this paper
• Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices

  2024cites this paper
• Fast White-Box Adversarial Streaming Without a Random Oracle

  2024cites this paper
• Revisiting lower dimension lattice attacks on NTRU

  2023cites this paper
• Post-Quantum Cryptosystems: Open Problems and Solutions. Lattice-Based Cryptosystems

  2023cites this paper
• Verification of NP-hardness Reduction Functions for Exact Lattice Problems

  2023cites this paper
• Improving Convergence and Practicality of Slide-type Reductions

  2023cites this paper
• The Complexity of the Shortest Vector Problem

  2023cites this paper
• 1 Further Reading 1 . 1 Maximum Feasible Linear System ( MAXFLS ) Problem 1

  2022influential citation
• Symmetry of information from meta-complexity

  2022cites this paper
• Lattice Problems beyond Polynomial Time

  2022cites this paper
• Report on the Security of LWE: Improved Dual Lattice Attack

  2022cites this paper
• Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms

  2022influential citation
• Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes

  2022cites this paper
• Approximability of Robust Network Design: The Directed Case

  2022cites this paper
• Approximate CVPp in time 20.802n

  2022cites this paper
• Improved Hardness of BDD and SVP Under Gap-(S)ETH

  2021cites this paper
• On the Smallest Ratio Problem of Lattice Bases

  2021cites this paper
• Approximate CVP in time 20.802 n - now in any norm!

  2021cites this paper
• On the Cryptographic Hardness of Learning Single Periodic Neurons

  2021cites this paper
• Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms

  2021cites this paper
• Revisiting Multivariate Ring Learning with Errors and its Applications on Lattice-based Cryptography

  2021cites this paper
• Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance

  2020cites this paper
• Approximate CVPp in Time 20.802 n

  2020cites this paper
• The nearest-colattice algorithm

  2020cites this paper
• The nearest-colattice algorithm

  2020cites this paper
• Hardness of bounded distance decoding on lattices in lp norms

  2020cites this paper
• Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

  2020cites this paper
• Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

  2020cites this paper
• Hardness of Approximate Nearest Neighbor Search under L-infinity

  2020cites this paper
• Approximate $\mathrm{CVP}_{p}$ in time $2^{0.802 \, n}$

  2020cites this paper
• Parameterized Intractability of Even Set and Shortest Vector Problem

  2019influential citation
• Solving Ring-LWE over Algebraic Integer Rings

  2019cites this paper
• The Projection Games Conjecture and the Hardness of Approximation of SSAT and related problems

  2019cites this paper
• Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in 𝓁p norm

  2019cites this paper
• Homomorphic lattice cryptosystems for secure signal processing

  2019cites this paper
• User-Controlled Computations in Untrusted Computing Environments

  2019cites this paper
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)

  2019cites this paper
• Approximation and Hardness: Beyond P and NP

  2019cites this paper
• The Projection Games Conjecture and the hardness of approximation of super-SAT and related problems

  2019cites this paper
• Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

  2018cites this paper
• Faster algorithms for SVP and CVP in the $\ell_{\infty}$ norm

  2018cites this paper
• New Constructions of Identity-Based and Key-Dependent Message Secure Encryption Schemes

  2018cites this paper
• Non-Black-Box Worst-Case to Average-Case Reductions within NP

  2018cites this paper
• On the Maximum Distance Sublattice Problem and Closest Vector Problem

  2018cites this paper
• SPACE-EFFICIENT CLASSICAL AND QUANTUM ALGORITHMS FOR THE SHORTEST

  2018cites this paper
• Zero-Knowledge Proof for Knowledge of RLWE (Ring-Learning with Errors) Secret Keys

  2018cites this paper
• Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm

  2018cites this paper
• Bin packing, number balancing, and rescaling linear programs

  2017cites this paper
• On the Quantitative Hardness of CVP

  2017cites this paper
• Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)

  2017cites this paper
• Space-efficient classical and quantum algorithms for the shortest vector problem

  2017cites this paper
• (Gap/S)ETH hardness of SVP

  2017influential citation
• Algorithms in Discrepancy Theory and Lattices

  2017cites this paper
• On the Gaussian Measure Over Lattices

  2017cites this paper
• Opleiding Informatica The closest vector problem in cyclotomic lattices

  2016cites this paper
• The Variant of Remote Set Problem on Lattices

  2016cites this paper
• Number Balancing is as Hard as Minkowski's Theorem and Shortest Vector

  2016cites this paper
• Key Exchange Protocol Based on Tensor Decomposition Problem

  2016cites this paper
• On the Lattice Distortion Problem

  2016cites this paper
• A Decade of Lattice Cryptography

  2016cites this paper
• The Systematic Normal Form of Lattices

  2016cites this paper
• Time-Memory Trade-Off for Lattice Enumeration in a Ball

  2016influential citation
• Hardness of Lattice Problems for Use in Cryptography

  2016cites this paper
• Discrete Gaussian Sampling Reduces to CVP and SVP

  2015cites this paper
• Inverse Optimization with Noisy Data

  2015cites this paper
• The remote set problem on lattices

  2015cites this paper
• Solving the Closest Vector Problem in $2^n$ Time - The Discrete Gaussian Strikes Again!

  2015cites this paper
• Solving Closest Vector Instances Using an Approximate Shortest Independent Vectors Oracle

  2015cites this paper
• Voronoi Cells of Lattices with Respect to Arbitrary Norms

  2015cites this paper
• On Promise Problem of the Generalized Shortest Vector Problem

  2015cites this paper
• Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One

  2015cites this paper
• Implementation and Comparison of Lattice-based Identification Protocols on Smart Cards and Microcontrollers

  2014cites this paper
• Lattice-Based Cryptography: Security Foundations and Constructions

  2014cites this paper
• LWE Encryption using LZW Compression

  2014cites this paper
• Generating a Lattice of a given Genus

  2014cites this paper
• Restricted parameter range promise set cover problems are easy

  2014cites this paper
• Locally Dense Codes

  2014influential citation
• Chiffrement avancé à partir du problème Learning With Errors

  2014cites this paper
• Advanced Cryptographic Primitives Course 3: The Learning With Errors Problem

  2014cites this paper
• On the Closest Vector Problem with a Distance Guarantee

  2014cites this paper
• Generating a Quadratic Forms from a Given Genus

  2014cites this paper
• On the Lattice Isomorphism Problem

  2013cites this paper
• Algorithms for the Shortest and Closest Lattice

  2013cites this paper
• Physical-layer cryptography through massive MIMO

  2013cites this paper
• On the foundations of key exchange

  2013cites this paper
• Algorithms for the Densest Sub-Lattice Problem

  2013cites this paper
• Physical-Layer Cryptography Through Massive MIMO

  2013cites this paper
• The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover

  2012cites this paper
• Lattice Sparsification and the Approximate Closest Vector Problem

  2012cites this paper