Polynomial-factor GapSVP ⇒ LWE (polynomial modulus)

Fully-black-box reduction · standard model · BLPRS13 · security loss: polynomial

Statement

There is a classical polynomial-time reduction from worst-case GapSVP within a polynomial factor on lattices of dimension $\Theta (\sqrt{n})$ to LWE in dimension $n$ with modulus $q=\mathrm{poly}(n)$ — BLPRS13. Hence if GapSVP is hard for polynomial factors, LWE with polynomial modulus is hard, the GapSVP dimension being the square root of the LWE dimension.

Notes

• The proof composes the exponential-modulus classical reduction of Pei09 with a modulus–dimension switching reduction, which reduces LWE in dimension $k$ with modulus exponential in $k$ to LWE in dimension $k^2$ with modulus polynomial in $k$ — BLPRS13.
• Regev’s quantum reduction reaches polynomial modulus without the dimension loss (GapSVP ⇒ LWE) — Reg05.