12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Two related definitions are around: zero knowledge and honest-verifier zero knowledge; difference basically is whether challenge is fixed (given to simulator). Simulator with real Verifier is required to produce proper distribution of challenge, so it it ZK, not HVZK. Such a simulator is expected polynomial time: some (small) probability exists for producing the same challenge for too many times. Difference is, expected time is polynomial in parameter. $\endgroup$ – Vadym Fedyukovych Aug 14 '15 at 10:02
  • $\begingroup$ As far as I know, the difference between zero-knowledge (ZK) and honest-verifier zero-knowledge (HVZK) were not the ones you mention, but rather that in ZK we consider the verifier to be potentially dishonest (and thus his challenge might not be random, but dependent on the commitment, for example), while in the HVZK the verifier is considered honest and thus his challenge is considered to be drawn at random. Then we have the distinction between HVZK and Special HVZK. In the "special" case, the simulator is given a challenge and it has to produce a valid transcript. $\endgroup$ – LRM Aug 14 '15 at 11:17
  • $\begingroup$ But still my question was more related to the simulator itself, on what it can or cannot do, within the particular case in which the verifier is assumed to be honest (i.e. his challenge will be random). $\endgroup$ – LRM Aug 14 '15 at 11:21
  • $\begingroup$ Difference is whether challenge is included into simulated "view" that should be indistinguishable from the view while running a protocol with real Prover. $\endgroup$ – Vadym Fedyukovych Aug 14 '15 at 11:37
  • $\begingroup$ One would prove expected polynomial time for a particular simulator, like one for graph 3-colorability language. $\endgroup$ – Vadym Fedyukovych Aug 14 '15 at 11:40
10
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Amazing answer, thanks a lot. Would then be correct to say that the expected running time of the simulator for the HVZK case is constant (a valid transcript is produced with only one run)? I wonder, though, why is the expected running time of M for the ZK case (with possibly dishonest verifier V*) polynomial? Wouldn't it be also constant (M succeeds after 2 attempts)? $\endgroup$ – LRM Aug 19 '15 at 8:23
  • $\begingroup$ Also, in your answer you're assuming that the challenge space has length 2, right? $\endgroup$ – LRM Aug 19 '15 at 8:27
  • 1
    $\begingroup$ Expected runtime for the HVZK simulator isn't really relevant, because the runtime is a fixed (not random) value, but technically its expectation is one attempt. It's not constant because each attempt takes some polynomial time. The only place I assume a challenge space of size 2 is at the end of my answer; if it's larger then the expected runtime increases commensurately. $\endgroup$ – Chris Peikert Aug 19 '15 at 11:51
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ While it's not "wrong" to use rewinding when proving that this protocol is HVZK, rewinding is not necessary (see my other answer). Avoiding rewinding means there's no need for an expected runtime analysis; the HVZK simulator can just be polynomial time. $\endgroup$ – Chris Peikert Aug 18 '15 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.