Time cost of security reduction
Even if $q_H$ and $q_{Sign}$ are $\mathsf{poly}(n)$, the security guarantees turn out meaningless since the loss is exponential in $q_{Sign}$. As the author points out in the paragraph (Page 18) following the proof of the theorem, $q_{Sign}$ has to be restricted to $o(n)$ so that security can be based on sub-exponential hardness of the underlying lattice problem.