## CryptoDB

### Paper: New (and Old) Proof Systems for Lattice Problems

Authors: Navid Alamati Chris Peikert Noah Stephens-Davidowitz DOI: 10.1007/978-3-319-76581-5_21 Search ePrint Search Google PKC 2018 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 $\textsf {GapSPP}$GapSPP of approximating the $\varepsilon$ε-smoothing parameter (for some $\varepsilon < 1/2$ε<1/2) of an n-dimensional lattice. The smoothing parameter is a key quantity in the study of lattices, and $\textsf {GapSPP}$GapSPP has been emerging as a core problem in lattice-based cryptography, e.g., in worst-case to average-case reductions. We show that $\textsf {GapSPP}$GapSPP admits SZK proofs for remarkably low approximation factors, improving on prior work by up to roughly $\sqrt{n}$n. Specifically:There is a noninteractive SZK proof for $O(\log (n) \sqrt{\log (1/\varepsilon )})$O(log(n)log(1/ε))-approximate $\textsf {GapSPP}$GapSPP. Moreover, for any negligible $\varepsilon$ε and a larger approximation factor $\widetilde{O}(\sqrt{n \log (1/\varepsilon )})$O~(nlog(1/ε)), 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})$O(logn+log(1/ε)/logn)-approximate coGapSPP. We show this by proving that $O(\log n)$O(logn)-approximate $\textsf {GapSPP}$GapSPP is in $\mathsf {coNP}$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})$O(n) factor, improving upon the prior best factor of $\omega (\sqrt{n \log n})$ω(nlogn).
##### BibTeX
@inproceedings{pkc-2018-28904,
title={New (and Old) Proof Systems for Lattice Problems},
booktitle={Public-Key Cryptography – PKC 2018},
series={Public-Key Cryptography – PKC 2018},
publisher={Springer},
volume={10770},
pages={619-643},
doi={10.1007/978-3-319-76581-5_21},
author={Navid Alamati and Chris Peikert and Noah Stephens-Davidowitz},
year=2018
}