Meta-heuristic approaches to solve shortest lattice vector problem

Abstract

We present the aptness of population based meta-heuristic approaches to compute a shortest non-zero vector in a lattice for solving the Shortest lattice Vector Problem (SVP). This problem has a great many applications such as optimization, communication theory, cryptography, etc. At the same time, SVP is notoriously hard to predict, both in terms of running time and output quality.

The SVP is known to be NP-hard under randomized reduction and there is no polynomial time solution for this problem. Though LLL algorithm is a polynomial time algorithm, it does not give the optimal solutions. In this paper, we present the application of Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) to solve the SVP on an appropriate search space. We have implemented the PSO, GA and LLL algorithm for the SVP. The comparison results shows that our algorithm works for all instances.

Subject Classification:

• (2000) cc:68T20

Keywords:

• Shortest Vector Problem
• Lattice Problems
• PSO
• GA