On the Maximum Distance Sublattice Problem and Closest Vector Problem

In this paper, we introduce the Maximum Distance Sublattice Problem (<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathsf{MDSP}$</tex>). We observed that the problem of solving an instance of the Closest Vector Problem (<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathsf{CVP}$</tex>) in a lattice <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{L}$</tex> is the same as solving an instance of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathsf{MDSP}$</tex> in the dual lattice of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{L}$</tex>. We give an alternate reduction between the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathsf{CVP}$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathsf{MDSP}$</tex>. This alternate reduction does not use the concept of dual lattice.