Paper 2017/1226

New (and Old) Proof Systems for Lattice Problems

Navid Alamati, Chris Peikert, and Noah Stephens-Davidowitz


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})$.

Available format(s)
Publication info
Published by the IACR in PKC 2018
lattices(noninteractive) statistical zero knowledgesmoothing parametercovering radius
Contact author(s)
alamati @ umich edu
2017-12-22: received
Short URL
Creative Commons Attribution


      author = {Navid Alamati and Chris Peikert and Noah Stephens-Davidowitz},
      title = {New (and Old) Proof Systems for Lattice Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1226},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.