Search LWE ⇒ Decision LWE

Standard model · Reg05 · security loss: polynomial: for a distinguisher of advantage $\epsilon$ the search algorithm runs in time $\mathrm{poly}(n,q,1/\epsilon )$, testing each of the $nq$ guesses $s_i=\ell$

Statement

Let $q=\mathrm{poly}(n)$ be prime. If search LWE with parameters $(n,q,\chi )$ is hard for every polynomial number of samples, then decision LWE with the same $(n,q,\chi )$ is hard for every polynomial number of samples: an efficient distinguisher between $(\mathbf{A},\mathbf{As}+\mathbf{e})$ and $(\mathbf{A},\mathbf{u})$ using $m$ samples yields an efficient algorithm that recovers $\mathbf{s}$ from $\mathrm{poly}(n,m)$ samples — Reg05. Sample-preserving search-to-decision reductions hold for a wide range of parameters: $m$ LWE samples are pseudorandom whenever search LWE is hard for the same $m$ — MM11b.

Sketch

To test the guess $s_i=\ell$, map each sample $(\mathbf{a},b)$ to $(\mathbf{a}+r{1}_i,b+r\ell )$ for the $i$-th unit vector $1_i$ and fresh uniform $r\in {\mathbb{Z}}_q$; the result is $({\mathbf{a}}^{\prime },⟨{\mathbf{a}}^{\prime },\mathbf{s}⟩+e+r(\ell -s_i))$, LWE-distributed if $\ell =s_i$ and uniform otherwise, since $q$ is prime. Running the distinguisher on all $nq$ pairs $(i,\ell )$, polynomially many because $q=\mathrm{poly}(n)$, reads off $\mathbf{s}$. Beforehand, the self-reduction $(\mathbf{a},b)\mapsto (\mathbf{a},b+⟨\mathbf{a},\mathbf{t}⟩)$ for uniform $\mathbf{t}$ turns a distinguisher for uniform $\mathbf{s}$ into one that works for every $\mathbf{s}$.

Notes

• The converse holds for every modulus, given an error distribution with efficiently recognizable support and enough samples — folklore; see Decision LWE ⇒ Search LWE.