LWE with sub-exponential ratio ⇒ LWR

Fully-black-box reduction · standard model · BPR12 · security loss: Additive: the LWR advantage exceeds the LWE advantage by at most $m\cdot O(pB/q)$ plus the probability that some error exceeds $B$, negligible for $q\ge pB\cdot n^{\omega (1)}$.

Statement

Let $\chi$ be $B$-bounded except with negligible probability, $p\ge 2$ and $q\ge pB\cdot n^{\omega (1)}$. Then decision LWR for $(n,q,p)$ with any $m=\mathrm{poly}(n)$ samples is at least as hard as decision LWE for $(n,q,\chi ,m)$ — BPR12. Under LWE with sub-exponential modulus-to-noise ratio, with Gaussian width $\alpha q$, $1/\alpha =2^{n^{\epsilon }}$ and $B=\alpha q\cdot \omega (\sqrt{\log n})$, taking $p=\lfloor 2^{n^{\epsilon }/2}\rfloor$ gives $q/(pB)=n^{\omega (1)}$, hence LWR hardness at the same modulus $q\le 2^{\mathrm{poly}(n)}$, with $q>p\ge 2$ and $q/p=n^{\omega (1)}$.

Sketch

Map each LWE sample $(\mathbf{a},b)$ to $(\mathbf{a},\lfloor b{\rceil }_p)$; a uniform $b$ maps to $\lfloor b{\rceil }_p$. For $b=⟨\mathbf{a},\mathbf{s}⟩+e$ with $|e|\le B$, $\lfloor b{\rceil }_p=\lfloor ⟨\mathbf{a},\mathbf{s}⟩{\rceil }_p$ unless $⟨\mathbf{a},\mathbf{s}⟩$ lies within $B$ of a rounding boundary, which for uniform $\mathbf{a}$ and all but a negligible fraction of secrets $\mathbf{s}$ happens with probability $O(pB/q)$; a union bound over the $m$ samples completes the reduction — BPR12.

Notes

• BPR12 introduce LWR to build pseudorandom functions computable by low-depth circuits, in ${\mathbf{NC}}^1$ or even ${\mathbf{TC}}^0$ — BPR12.