On the Lattice Smoothing Parameter Problem

Abstract

The smoothing parameter ${\eta }_{\epsilon }(\mathcal{L})$ of a Euclidean lattice $\mathcal{L}$, introduced by Micciancio and Regev (FOCS'04; SICOMP'07), is (informally) the smallest amount of Gaussian noise that "smooths out" the discrete structure of $\mathcal{L}$ (up to error $\epsilon$). It plays a central role in the best known worst-case/average-case reductions for lattice problems, a wealth of lattice-based cryptographic constructions, and (implicitly) the tightest known transference theorems for fundamental lattice quantities. In this work we initiate a study of the complexity of approximating the smoothing parameter to within a factor $\gamma$, denoted $\gamma$-$\mathrm{GapSPP}$. We show that (for $\epsilon =1/\mathrm{poly}(n)$): $(2+o(1))$-$\mathrm{GapSPP}\in \mathrm{AM}$, via a Gaussian analogue of the classic Goldreich-Goldwasser protocol (STOC'98); $(1+o(1))$-$\mathrm{GapSPP}\in \mathrm{coAM}$, via a careful application of the Goldwasser-Sipser (STOC'86) set size lower bound protocol to thin spherical shells; $(2+o(1))$-$\mathrm{GapSPP}\in \mathrm{SZK}\subseteq \mathrm{AM}\cap \mathrm{coAM}$ (where $\mathrm{SZK}$ is the class of problems having statistical zero-knowledge proofs), by constructing a suitable instance-dependent commitment scheme (for a slightly worse $o(1)$-term); $(1+o(1))$-$\mathrm{GapSPP}$ can be solved in deterministic $2^{O(n)}\mathrm{polylog}(1/\epsilon )$ time and $2^{O(n)}$ space. As an application, we demonstrate a tighter worst-case to average-case reduction for basing cryptography on the worst-case hardness of the $\mathrm{GapSPP}$ problem, with $\tilde{O}(\sqrt{n})$ smaller approximation factor than the $\mathrm{GapSVP}$ problem. Central to our results are two novel, and nearly tight, characterizations of the magnitude of discrete Gaussian sums.