Optimal bounding function for GNR-enumeration

The proposed pruning technique by Gama-Nguyen-Regev for enumeration function makes this pruned enumeration (GNR-enumeration) as a claimant practical solver for SVP. The total cost of GNR-enumeration over a specific input lattice block with pre-defined enumeration radius and success probability would be minimized, just if this enumeration uses an optimal bounding function for pruning. Unfortunately, the running time of the original proposed algorithm of searching optimal bounding function by the work of Chen-Nguyen (in 2011) is not analyzed at all, so our work in this paper tries to introduce some efficient searching algorithms with exact analysis of their time/space complexity. In fact, this paper proposes a global search algorithm to generate the optimal bounding function by a greedy idea. Then, by using our greedy strategy and defining the searching steps based on success probability, a practical search algorithm is introduced, while it’s time-complexity can be determined accurately. Main superiorities of our algorithm include: complexity analysis, using high-performance version of each sub-function in designing search algorithm, jumping from local optimums, simple heuristics to guide the search, trade-off between quality of output and running time by tuning parameters. Also by using the building blocks in our practical search algorithm, a high-quality and fast algorithm is designed to approximate the optimal bounding function.