CryptoDB
New (and Old) Proof Systems for Lattice Problems
| Authors: | |
|---|---|
| Download: | |
| Conference: | PKC 2018 |
| 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 $$\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
}