Short Integer Solution (SIS) is proved to be hard by reducing $\textrm{SIVP}_\gamma$ to SIS, i.e., if we solve SIS, then we can solve $\textrm{SIVP}_\gamma$.
Is there any way to reduce an instance of SIS to an instance of $\textrm{SIVP}_\gamma$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If $A\in\mathbb{Z}_p^{n \times m}$, then you can define $$\mathcal{L}=\{y\in\mathbb{Z}^m~:~Ay=0\,\bmod\,p\}.$$
$\mathcal{L}$ is an $m$-dimensional lattice, and if you solve (search) $SIVP_\gamma$ in this lattice, it implies that you found a vector $v$ (actually many such vectors) such that $Av=0\bmod\,p$ and $||v||\leq \gamma\cdot\lambda_m(\mathcal{L}).$ So that's a solution to SIS. When $m>n$ (say $m>2n$) and $A$ is uniformly random, you can actually tightly bound the value $\lambda_m(\mathcal{L})$ to be around (ignoring some constants) $$\lambda_m(\mathcal{L})\approx \sqrt{m}\cdot \det(\mathcal{L})^{1/m}=\sqrt{m}\cdot p^{n/m}.$$ So, in short, if you can solve $SIVP_\gamma$ for random lattices of the above form, then you can find short vectors $v$ such that $Av=0\bmod\,p$ with $||v||<\gamma\cdot\sqrt{m}\cdot p^{n/m}$.
