Module-SIVP ⇒ Module LWE

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

Statement

Solving the shortest independent vectors problem on module lattices of rank $d$ over the ring of integers of a degree-$n$ number field, in the worst case and to within polynomial approximation factors, reduces in quantum polynomial time to average-case Module LWE of rank $d$, in its search form and, for suitable moduli, its decision form — LS15. Rank $d=1$ is the Ring LWE reduction and $n=1$ recovers plain LWE.

Sketch

The iterative quantum step of Reg05, carried over to rank-$d$ module lattices: the Module LWE oracle solves bounded-distance decoding on the dual module lattice, a quantum Fourier step turns that decoder into a sampler of narrower discrete Gaussians over the primal, and iterating drives the Gaussian width down to the target approximation factor.

Notes

• The reduction to Module-SIS in the same paper is classical — LS15; see Module-SIVP ⇒ Module-SIS.