Security proof of schnorr identification scheme

I have studied the Schnorr identification scheme, and I came across the security proof.

My question is regarding the following: \begin{align} \text{Pr}\left[\text{DLog}_{\mathcal{A}',\mathcal{G}}\left(n\right)=1\right] &= \text{Pr}_{\omega,r_1,r_2}\left[ V\left(\omega,r_1\right)\wedge V\left(\omega,r_2\right)\wedge r_1\neq r_2 \right] \\ &\geq \text{Pr}_{\omega,r_1,r_2}\left[ V\left(\omega,r_1\right)\wedge V\left(\omega,r_2\right) \right]- \text{Pr}_{\omega,r_1,r_2}\left[r_1=r_2\right] \\ &= \sum\nolimits_{\omega}{ \text{Pr}\left[\omega\right]\cdot \left(\delta_\omega\right)^2}- 1/q \\ &\geq \left(\sum\nolimits_{\omega}{ \text{Pr}\left[\omega\right]\cdot \delta_\omega}\right )^2 -1/q \\ &= \delta\left(n\right)^2-1/q \end{align}

With $$\delta_\omega \stackrel{def}{=} \text{Pr}_r\left[V\left(\omega,r\right)=1\right]$$ being the probability that the adversary will succeed in the identification experiment given that we use $$\omega$$ (random choices) and $$r$$ (the challenge).

When we move from the 2nd row to the 3rd, we assume that the event that the adversary correctly responds to the challenge $$r_1$$ is independent of the event that the adversary correctly responds to the challenge $$r_2$$.

But, we have no knowledge on how $$\mathcal{A}$$ is acting - so how can we assume these events are independent?

1 Answer

I believe this is the 'Rewinding Lemma' part of Schoor identification security proof, and very well explained in the Boneh and Shoup book "A Graduate Course in Applied Cryptography", pgs 727-728.

An important aspect here is that we have to consider another adversary B, who emulates (grab a digital compiled version of A) and plays/interacts with A. (we can think of B as whoever wants to break the scheme, and presupposes the existence of A):

1. first, B plays the role of the verifier, and expect A (playing the prover role) send w;
2. B send r1, and wait for the A's answer;
3. B rewinds A, so that A’s internal state is exactly the same as it was at the end of step 1;
4. B sends a random and independent r2; waits for the A answer.

So B may be ignorant about how A works, but s/he is who sets A independent challenges/answers, and takes advantage of it.