Approximate Voronoi cells for lattices, revisited (Q2027268)

Lattice problems, such as the shortest and closest vector problems, remain difficult computationally even in the presence of a quantum computer. As such, these problems are of vital interest to cryptographers. The author examines the Voronoi cells approach to the closest vector problem. \textit{E. Doulgerakis} et al. [Lect. Notes Comput. Sci. 11505, 3--22 (2019; Zbl 1447.94033)] had given the problem of determining the exact asymptotics on the volume of Voronoi cells under the Guassian heuristic. The author solves this open problem and uses it to obtain improved upper bounds on the time complexity of the randomized iterative slicer. The author settles the open problem of obtaining a continuous trade off between the size of the advice and the query time complexity, since the time complexity with subexponential advice in this approach matches the worst case enumeration bounds and achieves the same asymptotic scaling as average case enumeration algorithms for the closest vector problem.