Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle

DOI10.1007/978-3-642-22935-0_16zbMath1343.68109MaRDI QIDQ3088093

Thomas Holenstein, Chandan K. Dubey

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_16

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11H06: Lattices and convex bodies (number-theoretic aspects)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• New bounds in some transference theorems in the geometry of numbers
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• Approximating CVP to within almost-polynomial factors is NP-hard
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• Hardness of approximating the shortest vector problem in lattices
• Minkowski's Convex Body Theorem and Integer Programming
• Public-key cryptosystems from the worst-case shortest vector problem
• A sieve algorithm for the shortest lattice vector problem
• New lattice-based cryptographic constructions