Proving an identification-scheme based on a digital signature is secure

I am trying to prove to myself that an identification scheme derived from a digital signature in a challenge/response manner is secure, based on the security of the digital signature scheme. I've found an informal proof in these lecture notes, but I'm struggling to formalize it with a reduction.

Let $\Sigma = (GEN, SIGN, VERIFY)$ be a digital signature scheme, and $\mathcal{ID}^{\Sigma} = (IDGEN, P, V)$ be an identification scheme derived from the digital signature, in particular:

• $IDGEN = GEN$
• The prover $P$ takes a keypair $(sk, pk)$, receives a challenge $r$ from the verifier $V$, and returns a signature $\sigma = SIGN(sk, r)$ over the message
• The verifier $V$ takes a public key, generates a random challenge $r \in \{0,1\}^m$, sends it to the prover, receives a signatures $\sigma$, and accepts the proof iff the signature verifies $VERIFY(pk, r, \sigma)$

It seems to me that the security of the identification scheme should reduce straightforwardly to the security of the underlying digital signature. So I attempt the following reduction.

Let $\mathcal{A}$ be an adversary that succeeds in an active impersonation attack against the identification scheme with $Adv(\mathcal{A})$. That is, $\mathcal{A}$ receives a public key $pk$ drawn from $(sk, pk) \xleftarrow{} IDGEN()$, gets to interact with a polynomial number of prover oracles instantiated with the private key $P_{(sk,pk)}(\cdot)$, and after losing oracle access, must convince an honest verifier $V_{pk}(\cdot)$ to accept. $Adv(\mathcal{A}) = \Pr[VERIFY(pk,r,\sigma)]$

We now construct an adversary $\beta$ that succeeds in breaking the security of the underlying digital signature. $\beta$ accepts a public key $pk$ from the digital signature challenger, and feeds it to $\mathcal{A}$. $\beta$ then simulates the prover oracles to $\mathcal{A}$ by receiving $q$ challenges $r_i$ from $\mathcal{A}$, asking the digital signature challenger to sign these challenges, receiving $\sigma_i = SIGN(sk, r_i)$, and sending back the signature to $\mathcal{A}$. After $\mathcal{A}$ is done interacting with the prover oracles, $\beta$ acts as the honest verifier to $\mathcal{A}$ by picking a random $r$, receiving a candidate signature $\sigma$, and verifying the signature $VERIFY(pk, r, \sigma)$. $\beta$ will also forward the signature $\sigma$ to the digital signature challenger. Note that $\beta$ will win the digital signature game if $\mathcal{A}$ succeeds in their impersonation attack, and the signature is over a challenge $r$ that $\beta$ has not asked to be signed earlier. That is, $Adv(\beta) = \Pr[VERIFY(pk,r,\sigma) \land (r,\sigma) \notin \{(r_i, \sigma_i)\}]$.

Now we need to relate the success of the digital signature adversary $\beta$ to the success of the id scheme adversary $\mathcal{A}$. So far I have,

• $Adv(\beta) = \Pr[VERIFY(pk,r,\sigma) \land (r,\sigma) \notin \{(r_i, \sigma_i)\}]$
• $\Pr[VERIFY(pk,r,\sigma)] = Adv(\mathcal{A})$
• $\Pr[(r,\sigma) \notin \{r_i, \sigma_i\}] = 1 - \frac{q}{2^m}$

It's not clear to me where to go from here. Ideally, I'd like some expression or inequality relating $Adv(\mathcal{A}), Adv(\beta)$ such that if the former is large, so is the latter.

We can use conditional probability to get something like $\Pr[VERIFY(pk,r,\sigma) \land (r,\sigma) \notin \{(r_i, \sigma_i)\}] = \Pr[VERIFY(pk,r,\sigma) \vert (r,\sigma) \notin \{(r_i, \sigma_i)\}] \times \Pr[(r,\sigma) \notin \{(r_i, \sigma_i)\}]$, but nailing down the first part of that product is hard. We could also use boole's inequality (union bound for intersections), but that gets us a rather trivial $\Pr[VERIFY(pk,r,\sigma) \land (r,\sigma) \notin \{(r_i, \sigma_i)\}] \geq \Pr[VERIFY(pk,r,\sigma)] + \Pr[(r,\sigma) \notin \{(r_i, \sigma_i)\}] - 1$

Been racking my brain at this for a while... it seems like the security should trivially follow but the math ain't mathing. Any thoughts?

Let event $A$ denote $VERIFY(pk,r,\sigma)$ and event $B$ denote $(r,\sigma) \notin \{r_i, \sigma_i\}$. Then, \begin{align}Adv(\mathcal{A})=\Pr[A]&=\Pr[A\wedge B] + \Pr[A\wedge \bar B] \\&\leq\Pr[A\wedge B]+ \frac{q}{2^m}\\&=Adv(\beta) + \frac{q}{2^m} \end{align} We have $Adv(\beta)\geq Adv(\mathcal{A})- \frac{q}{2^m}$ which is good enough for the reduction if $q$ is polynomial in $m$. The law of total probability is what I used on the first line.