On tiny-probability lattice enumeration

Lattice enumeration is a widely used framework for investigating the computational properties of lattices. Its tree-based algorithm (Kannan in: STOC. ACM, New York, pp 193-206, 1983; Fincke and Pohst in J Math Comput 44(170):463-471, 1985) to find vectors which meet specific conditions is a fundamental subroutine in various applications. However, its time complexity is typically super-exponential in the lattice rank, which motivated Schnorr et al. in the 1990s to find a trade-off between the time complexity and the success probability of finding a solution. This effort was revisited by Gama et al. (EUROCRYPT 2010. Lecture notes in computer science. Springer, vol 6110, pp 257-278, 2010) and led to the extreme pruning strategy, which offers exponential speedups. They proposed an efficient algorithm to output a pruning strategy and a predicted cost for any given success probability. In this paper, we present a practical situation in which the actual cost of pruned enumeration is significantly larger than the predicted cost, which precisely happens when the Gaussian heuristic fails: the number of lattice points in some cylinder intersection is much bigger than the ratio between the intersection volume and the lattice co-volume. This phenomenon occurs when pruning parameters are set for a very small success probability. The likely source of this occurrence is the confinement of the searching region to a subspace. To address this, we propose a modification to the cost prediction and an update to the discussion of the cost lower bound (Aono et al. in Advances in Cryptology-CRYPTO 2018. Springer, Cham, pp 608-637, 2018). The revised lower bounds are approximately 20-30 times larger than the previous ones in cryptographically used settings.