Hardness of approximating the shortest vector problem in lattices
From MaRDI portal
Publication:3546301
DOI10.1145/1089023.1089027zbMath1323.68301WikidataQ57567974 ScholiaQ57567974MaRDI QIDQ3546301
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
cryptography; lattices; approximation algorithms; shortest vector problem; hardness of approximation
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
Cryptography Based on Quadratic Forms: Complexity Considerations, Sampling methods for shortest vectors, closest vectors and successive minima, Post-quantum cryptography: lattice signatures, Unnamed Item, Quantum algorithms for algebraic problems, Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle, The Geometry of Lattice Cryptography, Bounding the sum of square roots via lattice reduction, Identification and signatures based on NP-hard problems of indefinite quadratic forms