4
$\begingroup$

Let $P$ be a prover willing to prove to a verifier $V$ that he knows a witness $w$ satisfying $(x,w) \in R$ for some relation $R$ and some common input $x$.

As found in the literature, $P$ can use a $\Sigma$-protocol for the relation $R$, defined as a 3-move protocol that satisfies the following properties:

  • Completeness.
  • Special soundness.
  • Special-honest verifier zero-knowledge.

My question is concerning the definition of the third property, which is the following:

Definition of Special-honest verifier zero-knowledge (as in the literature): There exists a polynomial-time simulator $M$, which on input $x$ and a challenge $e$, 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$.

Clearly, the special-honest verifier zero-knowledge has a probabilistic interpretation (as noted in the part ``...with the same probability distribution as...'') and I wonder what the implications are of omitting it.

In other words, what would be wrong or how this could affect the protocol if the special-honest verifier zero-knowledge property was defined as follows instead?

Alternative (and possibly wrong, but I’d like to understand why) definition of Special-honest verifier zero-knowledge: There exists a polynomial-time simulator $M$, which on input $x$ and a challenge $e$, outputs an accepting conversation of the form $(a,e,z)$.

This other definition doesn't mention probabilities distributions, just the fact that the transcript generated by the simulator should be accepted by the verifier. To me, this implicitly implies that the generated transcript will have to have the same probability distribution as a real transcript (the one obtained from a conversation between a honest prover $P$ and a honest verifier $V$), otherwise the verifier wouldn't be accepting it. Or am I wrong? Do you know of any example in which this is not the case, i.e. the transcript generated by the simulator is accepted by the verifier but still it doesn't have the same distribution as a real transcript?

Any help or clarification with this will be very much appreciated.

$\endgroup$
  • $\begingroup$ As discussed in the other question, simulated transcript must be indistinguishable (unconditionally, statistically, computationally) from view of Verifier having protocol run with a real Prover. For HVZK, indistinguishable from all transcripts having the same challenge. Simulator is running in expected polynomial time. $\endgroup$ – Vadym Fedyukovych Aug 14 '15 at 16:12
2
$\begingroup$

The probabilistic nature is not specific to special-honest verifier zero-knowledge but that's what zero-knowledge is about. With zero-knowledge you want to formulate that such an interactive proof does not leak any information besides the validity of the claim, as it is efficiently simulatable meaning that real and simulated transcripts are not distinguishable.

That a simulator produces accepting transcripts does not necessarily mean that this simulated transcript cannot be distinguished from a real interaction. Assume for instance an artificial simulator that always uses the same $a$ independent of the value $e$. So the transcript could be an accepting one, but one could distinguish transcripts coming from real interactions and simulated ones.

$\endgroup$
  • $\begingroup$ Thanks for your answer, it really makes sense. But I have one question related to this. If the simulator indeed managed to convince the verifier more than once by using the same $a$, as you mention, wouldn't that imply at the same time, by the Special Soundness property, that a knowledge extractor (or even the verifier itself) would then be able to obtain the witness, which would in turn be contradictory, since the simulator doesn't know it? I'm a bit confused. $\endgroup$ – LRM Aug 5 '15 at 7:28
  • 1
    $\begingroup$ @LRM Indeed, for such deterministic simulator the entire proof system would be pointless. This underlines that your alternative definition of special-honst-verifier zero-knowledge would lead to protocols for which you could show all properties, but which would be meaningless in practice (you could always trivially extract the witness). $\endgroup$ – DrLecter Aug 5 '15 at 8:25

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.