How does the simulator of the special-honest verifier zero-knowledge property works?

Question

I’m a bit confused about what the simulator of the special-honest verifier zero-knowledge property of a $\Sigma$-protocol is supposed/allowed to do and how to prove that it is indeed efficient (i.e. it runs in a time polynomial in the security parameter).

A 3-move protocol between a prover $P$ and a verifier $V$ is said to be Honest verifier zero-knowledge if there exists a polynomial-time simulator $M$, which on input $x$, it outputs an accepting conversation of the form $(a,e,z)$, with the same probability distribution as conversations between the honest $P, V$ on input $x$.

In order to prove this property, we need to define a simulator, which is usually given black-box access to a honest $V$ and has full control over all $V$'s input tapes (including its random tape). I've found in many papers the following sequence of steps:

 1. The simulator starts the verifier V: the verifier is given the common input x, 
    some auxiliary input and also the random input bits. 

 2. To simulate one iteration, the simulator executes the following loop:

  2a) Draws a uniformly random challenge e, uniformly random response z, 
      then computes the commitment a (using e and z), and finally sends the commitment 
      to the verifier V.

  2b) Gets the challenge e' from V. If e=e', then it outputs (a,e,z) and exits the loop. 
      Otherwise, it resets V to its state right after step 1 and the simulator starts 
      from step (2a) again.

It seems to me that the random bits of $V$ are chosen in step 1 and kept fixed for the rest of the simulation, so the verifier works deterministically and he will always send the same challenge $e^{\prime}$ after step 1.

If this is so, I wonder, in the case of a fail run, why is the simulator drawing a brand new challenge, response, etc. all over again in step (2a)? Isn't the simulator allowed to use the challenge it just saw coming from the verifier ($e^{\prime}$) as its own new guess of the verifier's challenge?

My second question is: How do we proof now that the simulator is efficient, that is, that the simulator will only need to run a time polynomial in the security parameter before being able to produce an accepting transcript with the correct distribution? According to the above reasoning, and assuming that the simulator is indeed allowed to use the verifier's challenge $e^{\prime}$ as its new guess of the challenge, wouldn't the simulator always need two runs at most, to generate a valid simulated transcript?

I hope these questions make sense.

EDIT:

Some days after I first asked the question, and after having seen that I didn’t get any answer, I’ve noticed a problem with the question I had raised. The sequence of steps I described are not the ones that a simulator would do in order to prove the property of Special-honest verifier zero-knowledge (otherwise the simulator would receive a challenge as input), but to prove the Honest verifier zero-knowledge property (without the “special” part). Therefore, I've edited the question so as to talk about the property of Honest Verifier Zero-Knowledge.

Answer 1

Even following your edits, there's still some confusion about honest verifier zero knowledge and plain-old (i.e., "possibly malicious verifier") zero knowledge, which is a much stronger property.

Your description of HVZK is essentially correct, but with the following clarifications:

A 3-move protocol between a prover P and a verifier V for a language $L$ is said to be honest verifier zero-knowledge if there exists a polynomial-time simulator $M$, which on any input $x$ in the language $L$, outputs a transcript $(a,e,z)$ having the same probability distribution as a conversation between the honest $P,V$ on input $x$.

A key point here is that the simulator's transcript must look like a real conversation between the honest prover and verifier. Typically, this makes simulation very straightforward, because in most protocols the honest verifier is defined to make a uniformly random challenge $e$ that is independent of the prover's initial message $a$. So the simulator does not need "black box" access to $V$ or its random tape, nor does it need to rewind $V$, because we know exactly how the honest $V$ operates. Instead, a typical simulator for proving HVZK will just first choose the challenge $e$ uniformly at random, then generate the prover's messages $a,z$ in a manner consistent with that challenge, and output the transcript straightaway (no rewinding). It's usually easy to prove that $(a,e,z)$ has the appropriate distribution, thanks to the independence of $a$ and $e$ in the real protocol.

By contrast, the strategy presented in steps 1-2(b) represents a typical (black-box) simulator for proving plain-old ("possibly malicious verifier") ZK. Here we don't know the verifier $V^*$'s strategy for choosing its challenge $e^*$; in particular, it might choose $e^*$ non-uniformly, or in a way that depends on the prover's first message. So we usually define a simulator $M$ that first "guesses" an $e$ in advance and prepares $a,z$ to work for that value of $e$, then sends $a$ to $V^*$ to receive some $e^*$, and checks whether $e=e^*$. If so, $M$ finishes the transcript successfully, otherwise it throws everything away and starts over.

To answer your first question, the reason $M$ starts over from scratch is that we don't know how $V^*$ chooses its $e^*$ -- maybe $e^*$ has some crazy dependence on the prover's first message $a$. In such a case, changing $a$ could lead to an entirely different challenge $e^*$ (even if $V^*$'s coins remain fixed).

To answer your second question, one can typically design $M$ so that when $x \in L$, the value $a$ that $M$ gives to $V^*$ reveals no information about which challenge $M$ is prepared to answer. So if, e.g., $e$ is a uniformly random bit, the probability that $e^*=e$ is exactly 1/2, and so $M$ succeeds after 2 attempts in expectation. This means that its expected runtime is polynomial. (Alternatively, one get a truly polynomial-time simulator that outputs a transcript that is statistically close to a real one between $P$ and $V^*$ -- the difference being that in the negligibly small chance that $M$ fails after many attempts, it just outputs a junk transcript.)

Answer 2

I've found some lecture notes where, in section 2.4, they give the steps that a simulator would do in order to simulate the view of the honest prover talking to the honest verifier (HVZK).

In response to the first question, in the case when the simulator initially guessed wrong the challenge coming from the verifier, the verifier is rewinded but the simulator DOES NOT draw a new challenge and expects it to be the same as the one coming from the verifier. Instead, the simulator uses the challenge sent from the verifier, knowing that after the rewind the verifier will again send the same challenge (due to the fact that the honest verifier uses only his random tape to choose the challenge).

As for the expected time that the given simulator would take to produce a valid transcript, the lecture notes mention that the simulator would make at most $2k$ steps to produce a valid transcript of length $k$ that is indistinguishable from a real conversation between the prover and the verifier.