Schnorr identification protocol security proof

Question

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:

1. Prover generates random $a_t\in G$ and sends $g^{a_t}$ to verifier
2. Verifier responds by sending random $c$ to the prover.
3. Prover responds by sending $a_z = a_t + c\,a$
4. 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?

Answer 1

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.

Answer 2

A very clear analysis of the security of the id-scheme of Schnorr was given by Damgard in his cource material here : http://www.daimi.au.dk/∼ivan/Sigma.pdf . The first analysis of the security was given by Schnorr in his paper : https://link.springer.com/chapter/10.1007/0-387-34805-0_22 [proposition 2.1] (both of them explain why you can always get a passing pair $(a_z,a_z').$)

The "rewind" is needed for the security proof. Remark that, the attack is probabilistic (and not determenistic) and the the whole security proof is the computation of the success probability $\mathcal{P}$ (in fact a lower bound is enough) to get a passing pair. So, in the final argument of the security proof, you get that, after $1/{\mathcal{P}}$ calls of the adversary ${\mathcal{A}}$ (which is a probabilistic polynomial algorithm) you can have a passing pair $(a_z,a_z'),$ with $a_z\not=a_z'$ and then you can easily find the discrete log.

Hope that helps.