Quantum polynomial-factor GapSVP ⇒ LWE

Fully-black-box reduction · quantum setting · Reg05 · security loss: polynomial

Statement

For $\alpha q>2\sqrt{n}$, an efficient algorithm solving LWE in dimension $n$ with modulus $q$ and Gaussian error parameter $\alpha$ on a noticeable fraction of instances yields an efficient quantum algorithm approximating worst-case GapSVP on $n$-dimensional lattices to within $\tilde{O}(n/\alpha )$ — Reg05; for decision LWE the modulus must be prime and $\mathrm{poly}(n)$. Hence if GapSVP is quantumly hard for polynomial factors, search and decision LWE are hard on average for every $\alpha \ge 1/\mathrm{poly}(n)$ with $\alpha q>2\sqrt{n}$.

Sketch

Given discrete Gaussian samples of parameter $r$ over a lattice $L$, the LWE oracle solves bounded-distance decoding on the dual $L^{\ast }$ to within distance $\alpha q/(\sqrt{2}r)$, and a quantum step turns this decoder into a sampler of discrete Gaussians over $L$ with parameter $r\sqrt{n}/(\alpha q)<r/2$. Iterating yields a sampler at parameter $\sqrt{2n}{\eta }_{\epsilon }(L)/\alpha$ for every lattice $L$, and such a sampler approximates GapSVP to within $\tilde{O}(n/\alpha )$.

Notes

• A classical reduction from worst-case GapSVP holds for exponential modulus $q\ge 2^{n/2}$ — Pei09.
• With polynomial modulus, LWE in dimension $n$ is classically as hard as worst-case GapSVP in dimension $\Theta (\sqrt{n})$, via modulus–dimension switching — BLPRS13.