Mithilesh Kumar, Havard Raddum, and Srimathi Varadharajan

Reducing Lattice Enumeration Search Trees

We revisit the standard enumeration algorithm for finding the shortest vectors in a lattice, and study how the number of nodes in the associated search tree can be reduced. Two approaches for reducing the number of nodes are suggested. First we show that different permutations of the basis vectors have a big effect on the running time of standard enumeration, and give a class of permutations that give relatively few nodes in the search tree. This leads to an algorithm called hybrid enumeration that has a better running time than standard enumeration when the lattice is large. Next we show that it is possible to estimate the signs of the coefficients yielding a shortest vector, and that a pruning strategy can be based on this fact. Sign-based pruning gives fewer nodes in the search tree, and never missed the shortest vector in the experiments we did.

Reference:
DOI: 10.36244/ICJ.2019.4.2

Download 

Please cite this paper the following way:

Mithilesh Kumar, Håvard Raddum and Srimathi Varadharajan, "Reducing Lattice Enumeration Search Trees",  Infocommunications Journal, Vol. XI, No 4, December 2019, pp. 8-16. DOI: 10.36244/ICJ.2019.4.2