On the Maximum Distance Sublattice Problem and Closest Vector Problem

2018/11/07 by Kumar, Rajendra, Mehta, Shashank K, Rajasree, Mahesh Sreekumar
#Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1811.03019

Abstract

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 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.

Related

• Lattice Sparsification and the Approximate Closest Vector Problem
• Improvements in closest point search based on dual HKZ-bases
• On Beating 2ⁿ for the Closest Vector Problem
• Solving the Closest Vector Problem with respect to l_p Norms
• The nearest-colattice algorithm