Ideal-SVP ⇒ Ring LWE

Fully-black-box reduction · quantum setting · LPR10 · security loss: polynomial: the quantum worst-case algorithm and the classical search-to-decision step run in polynomial time given any Ring LWE solver of noticeable advantage as an oracle

Statement

For the $m$-th cyclotomic field with ring of integers $R$ of degree $n$, there is a polynomial-time quantum reduction from worst-case approximate Ideal-SVP on ideal lattices in $R$, with approximation factor $\mathrm{poly}(n)$, to search Ring LWE over $R$ with Gaussian error; for prime $q=\mathrm{poly}(n)$ with $q\equiv 1(\mathrm{mod}m)$, a classical search-to-decision reduction extends the hardness to decision Ring LWE — LPR10. A direct quantum reduction from worst-case ideal-lattice problems to decision Ring LWE holds for any number field and any modulus — PRS17.

Sketch

The iterative quantum step of Reg05, carried over to ideal lattices: discrete Gaussian samples over an ideal lattice are turned into Ring LWE samples, the solver’s answers yield a bounded-distance decoder for the dual ideal, and a quantum step converts that decoder into samples from a narrower discrete Gaussian. Iterating shrinks the width until the samples contain a vector within a polynomial factor of the shortest.