Hash and sign via trapdoors for lattices

Question

Both the papers GPV'08 and MP'11 present trapdoors for lattices that allow to recover $s\in\mathbb{Z}_q^n$ and the error vector $e\in\mathbb{Z}_q^m$ when given $y=As+e$, for $A\in\mathbb{Z}_q^{m\times n}$.

Also, they claim that their constructions allow to construct signatures via the "hash and sign" paradigm. That is, given a random oracle $h:\{0,1\}^*\to \mathbb{Z}^m_q$, to sign a message $M$, the signer computes $$\mathsf{Sign}(\mathsf{td},M)=\mathsf{Invert}(h(M))=(s,e)$$ such that $As+e=h(M)$, where $\mathsf{td}$ is the trapdoor for $A$ and $\mathsf{Invert}$ is the inversion algorithm.

My questions are:

1. Does this means that there are a non-negligible number of words in $\mathbb{Z}_q^m$ that are decodable?
2. If so, every word in $\mathbb{Z}_q^m$ is decodable or we need to use a similar technique as in CFS'01, the McEliece based signature, where we need to try to decode $h(M,i)$ (for $i=0,1,2...$) several times, before getting a signature?

Answer 1

1. No: the parameter $m$ and the size $B$ of the coefficients of $(s,e)$ would not be the same in both scenarios. In the first (LWE decryption) the matrix $A$ is high and narrow, which makes the function `strongly injective', and decoding is possible. Most images do not have preimages, i.e., only a small fraction of $y$ are decodable, those corresponding to proper encryption. For (SIS) signature the matrix is wide and short, so that most images have many preimages. The term decodable should not be applied here nevertheless, since, well, the preimage is not unique.

2. No. There is no need to try several times, though care must be taken to avoid `learning attacks' such as this one. This is the role of Gaussian sampling.