**New (and Old) Proof Systems for Lattice Problems**

*Navid Alamati and 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 $\varepsilon$-smoothing
parameter (for some $\varepsilon < 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 $\sqrt{n}$. Specifically:

-- There is a *noninteractive* SZK proof for $O(\log(n) \sqrt{\log (1/\varepsilon)})$-approximate GapSPP. Moreover, for any negligible $\varepsilon$ and a larger approximation factor $\tilde{O}(\sqrt{n \log(1/\varepsilon)})$, there is such a proof with an *efficient prover*.

-- There is an (interactive) SZK proof with an efficient prover for $O(\log n + \sqrt{\log(1/\varepsilon)/\log n})$-approximate coGapSPP. We show this by proving that $O(\log n)$-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 $O(\sqrt{n})$ factor, improving upon the prior best factor of $\omega(\sqrt{n \log n})$.

**Category / Keywords: **foundations / lattices, (noninteractive) statistical zero knowledge, smoothing parameter, covering radius

**Original Publication**** (in the same form): **IACR-PKC-2018

**Date: **received 19 Dec 2017

**Contact author: **alamati at umich edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20171222:200823 (All versions of this report)

**Short URL: **ia.cr/2017/1226

[ Cryptology ePrint archive ]