Hardness of approximating the shortest vector problem in lattices

DOI10.1145/1089023.1089027zbMath1323.68301WikidataQ57567974 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

cryptography; lattices; approximation algorithms; shortest vector problem; hardness of approximation

Mathematics Subject Classification ID

94A60: Cryptography

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

94B15: Cyclic codes

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

11H71: Relations with coding theory

Related Items

Unnamed Item, Cryptography Based on Quadratic Forms: Complexity Considerations, Finding shortest lattice vectors faster using quantum search, Sampling methods for shortest vectors, closest vectors and successive minima, Restricted parameter range promise set cover problems are easy, The remote set problem on lattices, Post-quantum cryptography: lattice signatures, Improved analysis of the reduction from BDD to uSVP, Improved hardness results for unique shortest vector problem, Unnamed Item, Lattice Point Enumeration on Block Reduced Bases, Quantum algorithms for algebraic problems, Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle, The Geometry of Lattice Cryptography, Three Problems on Exponential Bases, Bounding the sum of square roots via lattice reduction, Identification and signatures based on NP-hard problems of indefinite quadratic forms