New (and old) proof systems for lattice problems. Alamati, N., Peikert, C., & Stephens-Davidowitz, N. In PKC, 2018.
New (and old) proof systems for lattice problems [link]Paper  abstract   bibtex   19 downloads  
$ \newcommand{Øtil}{\ensuremath{\widetilde{O}}} \newcommand{\problem}[1]{\ensuremath{\mathsf{#1}}} \newcommand{\gapspp}{\problem{GapSPP}} \newcommand{øNP}{\mathsf{coNP}} \newcommand{\eps}{ε} \newcommand{\ensuremath}[1]{#1} $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 $ε$-smoothing parameter (for some $ε < 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(łog(n) \sqrt{łog (1/\eps)})$-approximate $\gapspp$. Moreover, for any negligible $ε$ and a larger approximation factor $Øtil(\sqrt{n łog(1/\eps)})$, there is such a proof with an efficient prover. $•$ There is an (interactive) SZK proof with an efficient prover for $O(łog n + \sqrt{łog(1/\eps)/łog n})$-approximate $\problem{coGapSPP}$. We show this by proving that $O(łog n)$-approximate $\gapspp$ is in $øNP$. 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 $ω(\sqrt{n łog n})$.
@inproceedings{APSNewOld18,
  title = {New (and old) proof systems for lattice problems},
  abstract = {$
\newcommand{\Otil}{\ensuremath{\widetilde{O}}}
\newcommand{\problem}[1]{\ensuremath{\mathsf{#1}}}
\newcommand{\gapspp}{\problem{GapSPP}}
\newcommand{\oNP}{\mathsf{coNP}}
\newcommand{\eps}{\epsilon}
\newcommand{\ensuremath}[1]{#1}
$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 $\epsilon$-smoothing
parameter (for some $\epsilon < 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:

 $\bullet$  There is a noninteractive SZK proof for
$O(\log(n) \sqrt{\log (1/\eps)})$-approximate $\gapspp$.  Moreover,
for any negligible $\epsilon$ and a larger approximation factor
$\Otil(\sqrt{n \log(1/\eps)})$, there is such a proof with an
efficient prover.
 $\bullet$  There is an (interactive) SZK proof with an efficient prover for
$O(\log n + \sqrt{\log(1/\eps)/\log n})$-approximate
$\problem{coGapSPP}$.  We show this by proving that
$O(\log n)$-approximate $\gapspp$ is in $\oNP$.

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})$.},
  urldate = {2018-05-30},
  url = {https://eprint.iacr.org/2017/1226},
  booktitle = {PKC},
  author = {Alamati, Navid and Peikert, Chris and {Stephens-Davidowitz}, Noah},
  year = {2018}
}
Downloads: 19
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021