Improved hardness results for unique shortest vector problem

DOI10.1016/j.ipl.2016.05.003zbMath1362.68094arXiv1112.1564OpenAlexW2402835844MaRDI QIDQ2629774

Divesh Aggarwal, Chandan K. Dubey

Publication date: 7 July 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.1564

zbMATH Keywords

computational complexityreductionslatticesNP-hardnessunique SVP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice ⋮ Three Problems on Exponential Bases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials with rational coefficients
• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• On the limits of nonapproximability of lattice problems
• A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
• Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• Lattice problems in NP ∩ coNP
• Hardness of approximating the shortest vector problem in lattices
• Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
• New lattice-based cryptographic constructions
• On the unique shortest lattice vector problem

This page was built for publication: Improved hardness results for unique shortest vector problem