Q:

Schnorr identification protocol security proof

I read about security proof of Schnorr identification protocol against impersonation attack. For the sake of comprehensibility let me sum up the protocol: Given group $G$ with generator $g$. Verifier is initialized by prover's public key $g^a$, where the knowledge of secret counterpart is to be proven by prover. The protocol runs as following:

Prover generates random $a_t\in G$ and sends $g^{a_t}$ to verifier
Verifier responds by sending random $c$ to the prover.
Prover responds by sending $a_z = a_t + c\,a$
Verifier checks whether $g^{a_z}\overset{?}{=}g^{a_t}\,(g^a)^c$

Now, the idea of the security proof was: Given adversary $\mathcal{A}$ being able to issue valid $a_z'$ against arbitrary public key $g^{a'}$, we can turn $\mathcal{A}$ into an efficient $\mathrm{DLog}\,_g(g^{a'})$ oracle.
The proof assumed we can "rewind" the adversary so that it issues 2 different $a_z$'s with respect to a single $a_t$. I didn't understand this assumption. It seems somehow incomplete to me. What if I have non-cooperative adversary? This can't be turned into DLog oracle, since such adversary were indistinguishable from honest prover who knows secret key, thus breaking zero-knowledge protocol property. So is this a complete proof, which I merely didn't get or is the fact that malicious adversary might break the protocol without breaking DLog on $G$ essentially unprovable?

A:

It is important to understand that the simulator is a non-interactive machine; it does not interact with the prover (or with anybody else). What it can do is mimic (or simulate) a real interaction between the prover and the verifier, by playing the roles of both parties and internally "sending messages to itself". But it is not required to mimic the protocol exactly, only to produce an output that is close enough to the output of a real execution of the protocol. This is why it can internally repeat the protocol many times until it obtains a satisfactory output; there is no need for the prover to "cooperate", since again the simulator does not interact with the prover.

