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.


1 Answer 1


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.

  • $\begingroup$ Thanks, your answer is useful. I ingore the restriction for times of signature oracle. $\endgroup$
    – Alex Ideal
    Commented Apr 15, 2020 at 6:51

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.