Decision LWE ⇒ Search LWE

Fully-black-box reduction · standard model · folklore

Statement

Let $\chi$ have efficiently recognizable support (e.g. $\chi$ bounded), and let $m$ be large enough that $\delta :=\mathrm{Pr}\left[\exists \mathbf{s}:\mathbf{u}-\mathbf{As}\in \mathrm{supp}({\chi }^m)\right]$, over uniform $\mathbf{A}\in {\mathbb{Z}}_q^{m\times n}$ and $\mathbf{u}\in {\mathbb{Z}}_q^m$, is negligible. If decision LWE is hard for $(n,q,\chi ,m)$, then search LWE is hard for the same parameters: for every search solver $\mathcal{A}$ there is a distinguisher $\mathcal{B}$, running $\mathcal{A}$ once, with ${\mathbf{Adv}}_{n,q,\chi ,m,\mathcal{B}}^{\text{lwe}}(\lambda )\ge {\mathbf{Adv}}_{n,q,\chi ,m,\mathcal{A}}^{\text{slwe}}(\lambda )-\delta$ — folklore.

Sketch

Given $(\mathbf{A},\mathbf{u})$, $\mathcal{B}$ runs $\mathcal{A}$ to obtain $\hat{\mathbf{s}}$ and outputs “LWE” iff $\mathbf{u}-\mathbf{A}\hat{\mathbf{s}}$ lies in $\mathrm{supp}({\chi }^m)$. On LWE samples the check passes whenever $\mathcal{A}$ succeeds; on uniform samples it passes with probability at most $\delta$.

Notes

• The converse holds for prime $q=\mathrm{poly}(n)$, with polynomially more samples — Reg05; see Search LWE ⇒ Decision LWE.