On the Maximum Distance Sublattice Problem and Closest Vector Problem
This work addresses lattice-based cryptography and computational geometry problems, but appears incremental as it focuses on an alternate reduction between known problems.
The paper introduces the Maximum Distance Sublattice Problem (MDSP) and shows that solving the Closest Vector Problem (CVP) in a lattice is equivalent to solving MDSP in the dual lattice, providing an alternate reduction without using dual lattice concepts.
In this paper, we introduce the Maximum Distance Sublattice Problem (MDSP). We observed that the problem of solving an instance of the Closest Vector Problem (CVP) in a lattice $\mathcal{L}$ is the same as solving an instance of MDSP in the dual lattice of $\mathcal{L}$. We give an alternate reduction between the CVP and MDSP. This alternate reduction does not use the concept of dual lattice.