3
$\begingroup$

So a zero knowledge protocol (ZKP) is a protocol for which there exists an algorithm, called the simulator, which can produce, upon input of the statement(s) to be proven, but without a witness for the truth of the statement, transcripts indistinguishable from those resulting from interaction with the real prover.

My question is this:

How is this good?

Indeed, one advantage is that the protocol leaks no information of the prover (I guess that's why it's called zero knowledge) since it produce what the prover would have produced without passing through him.

But, that exactly means that any can pretend to be the prover. Which isn't very good.

Am I getting something wrong?

$\endgroup$
6
$\begingroup$

Here's the example I use sometimes.

Suppose I want to convince you that I am an excellent archer. If I show you a target painted on a wall, and an arrow in the bullseye of the target, are you convinced? No, since for all you know I could have fired the arrow first and then painted the target around it. In fact, even you could have done that, and you not a skilled archer. If instead you yourself paint the target first and watch me fire the arrow at the bullseye later, that's much more convincing.

So the "byproducts" of this interaction (the target and arrow) by themselves are not convincing. You could have generated them yourself (i.e., simulated them) even if you are an unskilled archer. Only if these byproducts were generated in a particular interactive way do they become convincing.

$\endgroup$
  • 1
    $\begingroup$ I really like this example! $\endgroup$ – dade Jan 20 '18 at 23:02
4
$\begingroup$

The point of the Zero Knowledge Proofs is not only do they reveal nothing beyond the assertion. But they provide compelling proof of the asserted statement. If the prover does not actually hold evidence to support his claim it should be computationally infeasible for him to mislead the verifier regarding the validity of the claim with non negligible probability. Someone without the evidence could produce a transcript. But will not be able to interact with a verifier and produce a convincing proof. The secret is in the interaction. Conversly if the proover can predict choices by the verifier he can mislead him. We assume the verifier has the ability to choose randomly hence the proof is convincing.

$\endgroup$
2
$\begingroup$

The important point here is that the simulator either can do something which the actual prover can not do, or gets some extra information which is not available to the actual prover. For example, in the context of Schnorr proofs in the discrete log setting the simulator can only produce transcripts which are identically distributed if it chooses the second message before fixing the first message. In proof systems which require a common reference string (CRS), one typically sets up the system in a way so that in addition to the CRS (which should be indistinguishable from the original setup) a simulation trapdoor is generated. Then the simulator additionally gets this simulation trapdoor.

So you are right, zero knowledge ensures that "no" information about the witness leaks. Below I will discuss why the simulator can not be used by anyone to pretend to be an actual prover knowing a witness.

The property, which prevents (among others) that anyone can use the simulator to pretend to be a prover who actually knows a witness for some statement, is called soundness. Here one requires that it is infeasible for any adversary to output a proof for a false statement. A stronger variant of soundness is called extractability, which requires the existence of an extractor which - when setting up the proof system in a "special way" - can extract a witness from every adversary who outputs a valid proof. Note that this does not conflict with zero knowledge as in zero knowledge one gives the simulator special privileges or some extra information which is not available to the soundness (extractability) adversary.

$\endgroup$
  • $\begingroup$ ok so the advantage I stated is correct and the disadvantage I stated is removed using the soundness property. $\endgroup$ – tomak Jan 20 '18 at 17:59
  • $\begingroup$ @tomak exactly - just updated my answer and made this explicit. $\endgroup$ – dade Jan 20 '18 at 18:02
  • $\begingroup$ You can assume soundness all you want. Is soundness actually possible in terms of implementation???? $\endgroup$ – user69816 Jun 12 at 0:14

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.