ISIS (Inhomogeneous SIS) ⇔ SIS

Equivalence · fully-black-box reduction · standard model · folklore

Statement

ISIS and SIS are equivalent up to a polynomial change of the column count and norm bound — folklore. One direction is immediate: if SIS is hard for $(n,m,q,\sqrt{{\beta }^2+1})$, then ISIS is hard for $(n,m-1,q,\beta )$. The other, ISIS hardness implying SIS hardness (solving ISIS with a SIS oracle), holds only under conditions on the column count and norm bound.

Sketch

Write a SIS instance as $\mathbf{A}=[{\mathbf{A}}^{\prime }\mid \mathbf{a}]$; then $({\mathbf{A}}^{\prime },\mathbf{a})$ is a uniform ISIS instance, and one ISIS-oracle call returning ${\mathbf{z}}^{\prime }$ with ${\mathbf{A}}^{\prime }{\mathbf{z}}^{\prime }=\mathbf{a}(\mathrm{mod}q)$ and $\Vert {\mathbf{z}}^{\prime }\Vert \le \beta$ gives the nonzero kernel vector $({\mathbf{z}}^{\prime },-1)$ of $\mathbf{A}$, of norm at most $\sqrt{{\beta }^2+1}$.