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$?


1 Answer 1


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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.