Tags:CVP, geometry, GSO, Karp reduction and lattice
Abstract:
In this paper, we introduced the Maximum Distance Sublattice Problem (MDSP). We observed that the problem of solving an instance of the Closest Vector Problem (CVP) in a lattice L is the same as solving an instance of MDSP in the dual lattice of L. We give an alternate reduction between the CVP and MDSP. This alternate reduction does not use the concept of dual lattice.
On the Maximum Distance Sublattice Problem and Closest Vector Problem