Module-SIVP ⇒ Module-SIS

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

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 classically to average-case Module-SIS of rank $d$ — LS15. Rank $d=1$ is the Ring-SIS reduction and $n=1$ recovers plain SIS.

Sketch

Ajtai’s iterative basis shortening (Ajt96) over modules: discrete Gaussian vectors of the worst-case module lattice, with their coordinates with respect to the current basis reduced mod $q$, form a nearly uniform Module-SIS instance, and a short solution $\mathbf{z}$ combines the samples into a lattice vector shorter than the longest current basis vector; iterating yields short independent vectors.