# Relation between decisional SIS and leftover hash lemma in lattices

The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\in \mathbb{Z}_q^{(n+1)\times m}$ and uniformly random $x \in \{0,1 \}^m$, the term $Ax\in \mathbb{Z}_q^{n+1}$ is close to uniform.

Now, I'm a little confused. I see no difference between this lemma and the hardness of decisional SIS problem. I think the condition on $m$ is also for being able to guarantee the existence of a solution for the corresponding SIS problem (and so having the right version of this problem).

Can someone explain this?

The leftover hash lemma (LHL) says that $(A,u=Ax) \in \mathbb{Z}_q^{(n+1) \times (m+1)}$ is very close to uniformly random. In particular, this implies that for uniformly random $(A,u)$, there exists a solution $x \in \{0,1\}^m$ to $Ax=u$ with very high probability. For if not, a significant fraction of $u$ values would admit no solution, hence the distribution of $Ax$ would not be close to uniform, because it never produces any of those $u$ values. (In fact, most $u$ will typically have many solutions.)
The "decisional SIS problem" is not a standard concept, because it's not so meaningful. If one were to define it, the problem would ask to distinguish between $(A,u=Ax)$ and uniformly random $(A,u)$. But by the above we know that's just impossible: the two distributions are very close, so they can't be told apart.
The computational SIS problem (in its inhomogeneous version) asks, given uniformly random $(A,u)$, to find some short (e.g., binary) $x$ such that $Ax=u$. Again, the choice of $m$ is such that solution(s) exist with very high probability; the computational question is whether we can efficiently find a solution.