Lattice Enumeration with Discrete Pruning: Improvement, Cost Estimation and Optimal Parameters

Lattice enumeration is a linear-space algorithm for solving the shortest lattice vector prob-lem(SVP). Extreme pruning is a practical technique for accelerating lattice enumeration, which has mature theoretical analysis and practical implementation. However, these works are still remain to be done for discrete pruning. In this paper, we improve the discrete pruned enumeration (DP enumeration), and give a solution to the problem proposed by L´eo Ducas et Damien Stehl´e [19] about the cost estimation of discrete pruning. Our contribution is on the following three aspects: First, we reﬁne the algorithm both from theoretical and practical aspects. Discrete pruning using natural number representation lies on a randomness assumption of lattice point distribution, which has an obvious paradox in the original analysis. We rectify this assumption to ﬁx the problem, and correspondingly modify some details of DP enumeration. We also improve the binary search algorithm for cell enumeration radius with polynomial time complexity, and reﬁne the cell decoding algorithm. Besides, we propose to use a truncated lattice reduction algorithm – k-tours-BKZ as reprocessing method when a round of enumeration failed. Second, we propose a cost estimation simulator for DP enumeration. Based on the investigation of lattice basis stability during reprocessing, we give a method to simulate the squared length of Gram-Schmidt orthogonalization basis quickly, and give the ﬁtted cost estimation formulae of sub-algorithms in CPU-cycles through intensive experiments. The success probability model is also modiﬁed based on the rectiﬁed assumption. We verify the cost estimation simulator on middle size SVP challenge instances, and the simulation results are very close to the actual performance of DP enumeration.Third,we give a method to calculate the optimal parameter setting to minimize the running time of DP enumeration. We compare the eﬃciency of our optimized DP enumeration with extreme pruning enumeration in solving SVP challenge instances. The experimental results in medium dimension and simulation results in high dimension both show that the discrete pruning method could outperform extreme pruning. An open-source implementation of DP enumeration with its simulator is also provided 1 .