Cryptology ePrint Archive: Report 2017/1226

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:

[ Cryptology ePrint archive ]