Welcome to the resource topic for
**2017/1226**

**Title:**

New (and Old) Proof Systems for Lattice Problems

**Authors:**
Navid Alamati, Chris Peikert, 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}).

**ePrint:**
https://eprint.iacr.org/2017/1226

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .