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
Related Tags
hardness-assumptions × 102discrete-logarithm × 17
diffie-hellman × 16
provable-security × 13
lattice-crypto × 12
factoring × 8
pairings × 8
complexity × 8
sis × 7
encryption × 6
number-theory × 6
public-key × 5
post-quantum-cryptography × 5
group-theory × 5
elliptic-curves × 4
rsa × 3
signature × 3
algorithm-design × 3
one-way-function × 3
lwe × 3
cryptanalysis × 2
homomorphic-encryption × 2
key-exchange × 2
modular-arithmetic × 2
chosen-plaintext-attack × 2