The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
From MaRDI portal
Publication:2719121
DOI10.1137/S0097539700373039zbMath0980.68054OpenAlexW2144593761WikidataQ57567486 ScholiaQ57567486MaRDI QIDQ2719121
Publication date: 21 June 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539700373039
Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Lattice points in specified regions (11P21) Approximation algorithms (68W25) Distribution of integers with specified multiplicative constraints (11N25)
Related Items (40)
Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ The inapproximability of lattice and coding problems with preprocessing ⋮ Anomaly-free sets of fermions ⋮ Application of automorphic forms to lattice problems ⋮ Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment ⋮ Improving the efficiency of the branch and bound algorithm for integer programming based on ``flatness information ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ Segment LLL reduction of lattice bases using modular arithmetic ⋮ A non-commutative cryptosystem based on quaternion algebras ⋮ Flat Tori with Large Laplacian Eigenvalues in Dimensions up to Eight ⋮ Revisiting lower dimension lattice attacks on NTRU ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Improving convergence and practicality of slide-type reductions ⋮ Patch Redundancy in Images: A Statistical Testing Framework and Some Applications ⋮ Gradual sub-lattice reduction and a new complexity for factoring polynomials ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Formalizing the LLL basis reduction algorithm and the LLL factorization algorithm in Isabelle/HOL ⋮ Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ A Parametric Version of LLL and Some Consequences: Parametric Shortest and Closest Vector Problems ⋮ Lower bounds of shortest vector lengths in random NTRU lattices ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ ETRU: NTRU over the Eisenstein integers ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors ⋮ Restricted parameter range promise set cover problems are easy ⋮ Fast LLL-type lattice reduction ⋮ Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms ⋮ On the unique shortest lattice vector problem ⋮ A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem ⋮ Quantum algorithms for algebraic problems ⋮ Sampling methods for shortest vectors, closest vectors and successive minima ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle ⋮ The Geometry of Lattice Cryptography ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor ⋮ Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
This page was built for publication: The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
