Reduction of decison SIS

Question

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?

Answer 1

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.