Reducing Lattice Enumeration Search Trees

Mithilesh, Kumar and Raddum, Havard and Varadharajan, Srimathi (2019) Reducing Lattice Enumeration Search Trees. INFOCOMMUNICATIONS JOURNAL, 11 (4). pp. 8-16. ISSN 2061-2079

Preview

Text InfocomJ_2019_4_2_Kumar.pdf Download (1MB) | Preview

Abstract

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.

Actions (login required)

Edit Item