SIVP ⇒ 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 SIVP 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 SIVP is hard in the worst case for efficient quantum algorithms, search and decision LWE are hard on average.

Sketch

Given discrete Gaussian samples of parameter $r$ over the input 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 shrinks the parameter to $\sqrt{2n}{\eta }_{\epsilon }(L)/\alpha$, where polynomially many samples contain $n$ linearly independent vectors of length $\tilde{O}(n/\alpha )\cdot {\lambda }_n(L)$.