The smoothing parameter eta_eps(L) of a Euclidean lattice L, introduced by Micciancio and Regev, is (informally) the smallest amount of Gaussian noise that “smooths out” the discrete structure of L (up to error eps). 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, denoted GapSPP. For our main result, we show that for the range eps = 1/poly(n) - a large cryptographically "interesting" range - there is statistical zero knowledge protocol for solving GapSPP to within a factor 2+o(1). Furthermore, we show that the hardness of the Learning with Errors (LWE) problem, which underlies many cryptographic primitives in lattice based crypto, can be based on the hardness of approximating the smoothing parameter to within a O(sqrt(n)/alpha) factor (alpha quantifies the LWE error). Compared to the reductions from GapSVP to LWE, we gain a sqrt(n) in the approximation factor.

Our main results are based on a new analysis of the classic Goldreich-Goldwasser protocol, originally designed to show that the problems of approximating the Shortest Vector & Closest Vector Problems to within O(sqrt(n / log n)) are in coAM. Using two new geometric characterizations of the smoothing parameter, we show that (variants) of the Goldreich-Goldwasser protocol can be adapted to give much tighter approximation factors for GapSPP.

Based on joint work with K.M. Chung, F.H. Liu, and C. Peikert.