2
$\begingroup$

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 ther any way to reduce an instance SIS to an instance of $\textrm{SIVP}_\gamma$?

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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