1
Write $A = [A_1 ~~ A_2]$ with
$A_1 \in \mathbb{Z}_q^{n\times m'}$
and
$A_2 \in \mathbb{Z}_q^{n\times (m-m')}$.
Likewise, $e = (e_1 ~~ e_2)$ with
$e_1 \in \mathbb{Z}_q^{m'}$
and
$e_2 \in \mathbb{Z}_q^{m-m'}$.
Then,
$$Ae = 0 \bmod q \iff A_2e_2 = -A_1e_1 \bmod q.$$
So, given an instance of SIS, that is, an $n\times m$ matrix $A$,
if you have an oracle to solve ...
Only top voted, non community-wiki answers of a minimum length are eligible
