## CryptoDB

### Noah Stephens-Davidowitz

#### Publications

Year
Venue
Title
2018
PKC
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).
2016
CRYPTO
2015
EPRINT
2015
EUROCRYPT
2014
CRYPTO
2014
EPRINT

TCC 2019
Crypto 2018

#### Coauthors

Navid Alamati (1)
Yevgeniy Dodis (4)
Ilya Mironov (3)
Chris Peikert (1)
Adi Shamir (2)
Daniel Wichs (2)