Hardness of approximating the shortest vector problem in lattices

DOI10.1145/1089023.1089027zbMath1323.68301DBLPjournals/jacm/Khot05OpenAlexW2056492141WikidataQ57567974 ScholiaQ57567974MaRDI QIDQ3546301

Subhash A. Khot

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1089023.1089027

zbMATH Keywords

cryptographylatticesapproximation algorithmsshortest vector problemhardness of approximation

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Cyclic codes (94B15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Relations with coding theory (11H71)

Related Items (31)

Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Improved hardness results for unique shortest vector problem ⋮ Post-quantum cryptography: lattice signatures ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ Lattice Point Enumeration on Block Reduced Bases ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Improved analysis of the reduction from BDD to uSVP ⋮ Revisiting lower dimension lattice attacks on NTRU ⋮ Improving convergence and practicality of slide-type reductions ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Vulnerable public keys in NTRU cryptosystem ⋮ Restricted parameter range promise set cover problems are easy ⋮ Bounding the sum of square roots via lattice reduction ⋮ Verification of NP-Hardness Reduction Functions for Exact Lattice Problems ⋮ Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_p\) norms ⋮ Lattice problems beyond polynomial time ⋮ Identification and signatures based on NP-hard problems of indefinite quadratic forms ⋮ 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 ⋮ Unnamed Item ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ Three Problems on Exponential Bases ⋮ Cryptography Based on Quadratic Forms: Complexity Considerations ⋮ The remote set problem on lattices

This page was built for publication: Hardness of approximating the shortest vector problem in lattices