SIVP ⇒ SIS

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

Statement

For a fixed polynomial factor $\gamma =n^{O(1)}$ and suitable $q,m=\mathrm{poly}(n)$, an efficient algorithm solving SIS with noticeable probability over uniform $\mathbf{A}\in {\mathbb{Z}}_q^{n\times m}$ yields an efficient classical algorithm that on every $n$-dimensional lattice outputs $n$ linearly independent lattice vectors whose longest is within $\gamma$ of optimal, that is, solves SIVP — Ajt96. Hence worst-case hardness of ${\mathrm{SIVP}}_{\gamma }$ implies average-case hardness of SIS. MR07 tighten the factor, for SIVP and GapSVP, to $\gamma =\beta \cdot \tilde{O}(\sqrt{n})$ for SIS norm bound $\beta$, any $m=\mathrm{poly}(n)$ and sufficiently large $q\ge \beta \cdot \mathrm{poly}(n)$, using Gaussian measures; GPV08 lower the modulus to $q\ge \beta \cdot \tilde{O}(\sqrt{n})$ with the same factor.

Sketch

Each step samples $m$ points ${\mathbf{y}}_i$ of the input lattice $L$ from a wide distribution and lets the columns of $\mathbf{A}$ be their coordinates with respect to the current basis, reduced mod $q$, which makes $\mathbf{A}$ nearly uniform; a short $\mathbf{z}$ with $\mathbf{Az}=0\mathrm{mod}q$ puts ${\sum }_i{z}_i{\mathbf{y}}_i$ in $qL$, and $\frac{1}{q}{\sum }_i{z}_i{\mathbf{y}}_i$ is a vector of $L$ shorter than the longest basis vector. Collecting $n$ independent such vectors and iterating shortens the basis until it is within a polynomial factor of ${\lambda }_n$; its vectors are the independent set.