Paper 2017/1226

New (and Old) Proof Systems for Lattice Problems

Navid Alamati, Chris Peikert, and Noah Stephens-Davidowitz

Abstract

We continue the study of statistical zero-knowledge (SZK) proofs, both interactive and noninteractive, for computational problems on point lattices. We are particularly interested in the problem GapSPP of approximating the $\epsilon$-smoothing parameter (for some $\epsilon <1/2$) of an $n$-dimensional lattice. The smoothing parameter is a key quantity in the study of lattices, and GapSPP has been emerging as a core problem in lattice-based cryptography, e.g., in worst-case to average-case reductions. We show that GapSPP admits SZK proofs for *remarkably low* approximation factors, improving on prior work by up to roughly $$. Specifically: -- There is a *noninteractive* SZK proof for $$-approximate GapSPP. Moreover, for any negligible $$ and a larger approximation factor $$, there is such a proof with an *efficient prover*. -- There is an (interactive) SZK proof with an efficient prover for $$-approximate coGapSPP. We show this by proving that $$-approximate GapSPP is in coNP. In addition, we give an (interactive) SZK proof with an efficient prover for approximating the lattice *covering radius* to within an $$ factor, improving upon the prior best factor of $$.