Hardness of approximating the shortest vector problem in lattices
From MaRDI portal
Publication:3546301
DOI10.1145/1089023.1089027zbMath1323.68301OpenAlexW2056492141WikidataQ57567974 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 (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 (28)
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 ⋮ 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
