Polynomial-factor GapSVP ⇒ 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 estimates ${\lambda }_1$ to within $\gamma$, that is, solves ${\mathrm{GapSVP}}_{\gamma }$, on every $n$-dimensional lattice — Ajt96. Hence worst-case hardness of GapSVP for polynomial factors implies average-case hardness of SIS. MR07 tighten the factor, for GapSVP and SIVP, to $\gamma =\beta \cdot \tilde{O}(\sqrt{n})$ for SIS norm bound $\beta$, which is $\tilde{O}(n)$ at the smallest admissible $\beta =\tilde{O}(\sqrt{n})$, using Gaussian measures.

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 to within a polynomial factor of ${\lambda }_n$. Run on the dual lattice $L^{\ast }$, this estimates ${\lambda }_n(L^{\ast })$, and transference, $1\le {\lambda }_1(L){\lambda }_n(L^{\ast })\le n$, turns that into an estimate of ${\lambda }_1(L)$ within a polynomial factor.