### 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 $\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)
Category
Foundations
Publication info
Keywords
lattices(noninteractive) statistical zero knowledgesmoothing parametercovering radius
Contact author(s)
alamati @ umich edu
History
Short URL
https://ia.cr/2017/1226

CC BY

BibTeX

@misc{cryptoeprint:2017/1226,
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{https://eprint.iacr.org/2017/1226}},
url = {https://eprint.iacr.org/2017/1226}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.