Polynomial-factor GapSVP ⇒ LWE (exponential modulus)

Fully-black-box reduction · standard model · Pei09 · security loss: polynomial: the worst-case algorithm runs in polynomial time given any LWE solver of noticeable success probability as an oracle

Statement

There is a classical probabilistic polynomial-time reduction from worst-case ${\mathrm{GapSVP}}_{\gamma }$ on $n$-dimensional lattices, $\gamma =\tilde{O}(n/\alpha )$, to search LWE in dimension $n$ with Gaussian error rate $\alpha$ and modulus $q\ge 2^{n/2}$; for $q$ a product of distinct primes of size $\mathrm{poly}(n)$, search and decision LWE are equivalent, so decision LWE is as hard — Pei09. Hence if GapSVP is hard for polynomial factors, LWE is hard for every inverse-polynomial $\alpha$ at such moduli.

Notes

• For moduli down to $q\ge n/\alpha$, search LWE is as hard as a variant of GapSVP with an extra parameter $\zeta$, $\zeta$-to-$\gamma$-GapSVP, which is equivalent to standard GapSVP for $\zeta \ge 2^{n/2}$ — Pei09.
• Polynomial moduli are reached classically at the cost of dimension (Polynomial-factor GapSVP ⇒ LWE (polynomial modulus)) — BLPRS13; quantumly, without that loss (GapSVP ⇒ LWE) — Reg05.