2014/12/26 by Kai-Min Chung, Daniel Dadush, Chung, Kai-Min +5 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1412.7979
arxiv created 2014/12/26 · arxiv updated 2014/12/30
The smoothing parameter ηε(L) of a Euclidean lattice 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 L (up to error ε). 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 γ, denoted γ-\rm GapSPP. We show that (for ε= 1/\rm poly(n)): (2+o(1))-\rm GapSPP ∈ \rm AM, via a Gaussian analogue of the classic Goldreich-Goldwasser protocol (STOC'98); (1+o(1))-\rm GapSPP ∈ \rm coAM, via a careful application of the Goldwasser-Sipser (STOC'86) set size lower bound protocol to thin spherical shells; (2+o(1))-\rm GapSPP ∈ \rm SZK ⊆ \rm AM ∩ \rm coAM (where \rm 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))-\rm GapSPP can be solved in deterministic 2O(n) \rm polylog(1/ε) time and 2O(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 \rm GapSPP problem, with O(√(n)) smaller approximation factor than the \rm GapSVP problem. Central to our results are two novel, and nearly tight, characterizations of the magnitude of discrete Gaussian sums.