# Time cost of security reduction

The following theorem is the description of one-more unforgeability in the paper lattice based blind signatures. I want to ask if the time $$t^{'}$$ is an exponential time since the $$q_{H}$$ and $$q_{Sign}$$ are about $$2^{60}$$. If the time $$t^{'}$$ is an exponential time then the adversary acturally cannot solve the hard problem, namely there is no contradiction exist.

Theorem 3.8 (One-more unforgeability. Let $$\text{Sign}$$ be the signature oracle. Let $$T_{\text{Sign}}$$ and $$T_\text{H}$$ be the cost functions for simulating the oracles $$\text{Sign}$$ and $$\text{H}$$, and let $$c \lt 1$$ be the probability for a restart in the protocol. $$\text{BS}$$ is $$(t, q_\text{Sign}, q_\text{H}, \delta)$$-one-more unforgeable if $$\text{com}$$ is $$(t', \delta / 2)$$-binding and $$Col(\mathcal{H}(\mathcal{R}, m), D)$$ is $$(t', \delta / 2)$$-hard with $$t' = t + q_{\text{H}}^{q_\text{Sign}}(q_\text{Sign}T_\text{Sign} + q_\text{H}T_\text{H})$$ and non-negligible $$\delta'$$ if $$\delta$$ is non-negligible.

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.