# Reduction of decison SIS

In Lyu12, Lemma 3.6 is as follows.

Lemma 3.6 For any non-negative integer $$\alpha$$ such that $$gcd(2\alpha+1, q)=1$$, there is a polynomial time reduction from the $$SIS_{q, n, m, d}$$ decsion problem to the $$SIS_{q, n, m, (2\alpha+1)d+\alpha}$$ decision problem.

Proof. To prove the lemma, we will show a transformation that maps the $$SIS_{q, n, m, d}$$ distribution to the $$SIS_{q, n, m, (2\alpha+1)d+\alpha}$$ distribution, and maps the uniform distribution over $$\mathbb{Z}^{n\times m}_{q}\times \mathbb{Z}^{n}_{q}$$ to itself. Given $$(A, t)$$, create a random vector $$r \stackrel{\}{\leftarrow} \{-\alpha, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, \alpha \}^{m}$$ and output $$(A, (2\alpha+1)t+Ar)$$. First observe that because $$2\alpha+1$$ is relatively prime to $$q$$, our transformation maps the uniform distribution to itself. And if $$(A, t)$$ canme form the $$SIS_{q, n, m, d}$$ distribution, then $$(2\alpha+1)t+Ar=A((2\alpha+1)S+r)$$, and since $$s$$ was chosen from the uniformly at random from $$\{-d, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, d \}^{m}$$, it's not hard to see that $$(2\alpha+1)S+r)$$ is uniformly random in $$\{-(2\alpha+1)d-\alpha, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, (2\alpha+1)d+\alpha \}^{m}$$.

I don't know the role of $$gcd(2\alpha+1, q)=1$$ in the proof. Why not create an problem $$SIS_{q, n, m, d+\alpha}$$ and reduces $$SIS_{q, n, m, d}$$ decsion problem to the $$SIS_{q, n, m, d+\alpha}$$ decision problem?

The assumption about gcd tell you that $$2\alpha +1$$ cannot belong to an ideal of $$\mathbb{Z}/q\mathbb{Z}$$. For example, $$2\alpha +1$$ could divide $$q$$ and then $$(2\alpha+1)t$$ is never going to look like a uniformly random vector in $$\mathbb{Z}_q^n$$. If you want to fix ideas, assume $$3$$ divides $$q$$ and $$\alpha =1$$: then $$(2\alpha+1)t$$ always has its entries a multiple of $$3$$, which is absolutely not what a uniform vector would look like. The added contribution of $$Ar$$ may not be enough to "blur" the entries to a more uniformly random vector: it is likely that you could observe too many instances where $$(2\alpha+1)t+Ar$$ has entries a multiple of $$3$$.
In general, having this assumption make the proof easier (it might even not be possible to have a general proof without it) and relax the care on $$\alpha$$. It is also not very restrictive.