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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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