On the Maximum Distance Sublattice Problem and Closest Vector Problem

EasyChair Preprint 14971

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.

Keyphrases: CVP, GSO, Karp reduction, geometry, lattice

@booklet{EasyChair:14971,
  author    = {Rajendra Kumar and Shashank Mehta and Mahesh Rajasree},
  title     = {On the Maximum Distance Sublattice Problem and Closest Vector Problem},
  howpublished = {EasyChair Preprint 14971},
  year      = {EasyChair, 2024}}