Optimal Sample Exponents for Direct Discrete-Gaussian SVP Search on Haar Random Lattices

Source abstract

We determine the optimal sample exponent for direct discrete Gaussian SVP search on Haar random unimodular lattices, counting zero outputs. The output is one sampled vector, optionally divided by the greatest common divisor of its lattice coordinates. For every fixed approximation factor $1\leqγ<\sqrt e$, the exponent is $γ^2/(2e)-\logγ$ in natural logarithmic units; it is zero for $γ\geq\sqrt e$. For exact SVP this gives $0.2653689\ldots$ in base two. The converse permits arbitrary positive widths chosen from the lattice and all previous outputs, and a fixed width attains every exponent above the threshold. Aggarwal, Dadush, Regev, and Stephens-Davidowitz already give a width within a factor two of optimal for exact SVP on each lattice. We determine the explicit Haar typical rate and show that primitive reduction preserves it. An explicit finite dimensional converse controls all widths simultaneously, including recovery from long multiples; together with finite attainment bounds, it yields query guarantees in both directions. The proof uses random lattice moments and a pointwise Gaussian bound optimized over the width. We account for sampling error and separate sample requirements from generation costs in comparisons with the random lattice search of Pouly and Shen and later algorithms.