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 .