Paper 2017/1226
New (and Old) Proof Systems for Lattice Problems
Navid Alamati, Chris Peikert, and Noah StephensDavidowitz
Abstract
We continue the study of statistical zeroknowledge (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 latticebased cryptography, e.g., in worstcase to averagecase 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})$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published by the IACR in PKC 2018
 Keywords
 lattices(noninteractive) statistical zero knowledgesmoothing parametercovering radius
 Contact author(s)
 alamati @ umich edu
 History
 20171222: received
 Short URL
 https://ia.cr/2017/1226
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/1226, author = {Navid Alamati and Chris Peikert and Noah StephensDavidowitz}, 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} }