So I was reading about ZKP on wikipedia, the abstract example in summary goes like this:

Peggy wants to prove to Victor that she knows the secret to a door inside a cave that connect A and B together (see diagram) without revealing the secret word to Victor.

  • Peggy takes a random entry not know to Victor
  • Victor shouts to Peggy to come out of path A or B (randomly choosen)
  • and so it follows that she must know the secret word in order to come out of the path that Victor chooses without revealing to Victor the secret word. Victor builds confidences the more times this is done.

However, why is Victor not allowed to see which path Peggy chooses to enter from? As this does not reveal any extra information about what the secret word is.

Why can't Victor see which way she enters and asks her to demonstrate the 4 possibilities, that is:

  • Enter from A and exit from A
  • Enter from A and exit from B
  • Enter from B and exit from A
  • Enter from B and exit from B

I believe this is done to illustrate two things.

(i) The small probability, that $P$eggy ($P$rover) might be lying. If she really does not know the magic word and $V$ictor ($V$erifier) sees her taking Path $A$, he would always ask her to come back via path $B$, thus the probability of $P$ succeeding when cheating is $0$.

However, $ZKP$s usually involve a small chance of $P$ succeeding while cheating, which is illustrated by $V$ not seeing the path $P$ takes to get to the magic door.

(ii) $V$ does not learn the secret. If $V$ stands at the crossroad of the paths $A$ and $B$, while $P$ walks to the magic door to say her magic word, it might be conceivable for $V$ to be able to hear $P$ saying her secret word. The only way to make sure that $V$ does not learn the magic word, is for him to wait outside of the cave, until $P$ has chosen a path.

  • $\begingroup$ (i) why are we not allowed to have the probability of P succeeding when cheating to 0, wouldn't that be ideal? (ii) He still won't know the secret, he watches her go in, shouts which exit to come out of, and then watches her exit. (rather than turning his back when she goes in and watching her come out) $\endgroup$ – Brandon Jun 8 '16 at 0:14
  • $\begingroup$ (i) Sure, this would be ideal. Usually, however, this is not the case for real $ZKP$ systems. (ii) It's just a matter of semantics, he might be able to hear her say the magic word, when he is standing at the crossroads of paths $A$ and $B$. $P$ wants to prevent this and asks $V$ to wait outside of the cave. $\endgroup$ – Riyil Jun 8 '16 at 7:24
  • $\begingroup$ (i) yes it seems ZKP systems are usually based on small probabilities but this might be due to the fact it's hard to come up with a perfect zero knowledge scenario like the one I stated rather than being a property itself of ZKP. After all ZKP require it to be complete, sound and zero knowledge, but nothing to do with 'a small chance of P succeeding while cheating?' unless my understanding of ZKP is wrong. $\endgroup$ – Brandon Jun 8 '16 at 9:45
  • $\begingroup$ (ii) But V could watch from a distance and then shout whether to come from A or B. If your going to say V might be able to hear from that distance, whats us to say that V pretends to turn around, then creeps forward when Peggy is in the cave and listen in? Both cases are equally probable and I'm not sure the purpose of turning away when Peggy goes in is to do with anything about accidentally or intentionally hearing the secret word. $\endgroup$ – Brandon Jun 8 '16 at 9:45

The article tries to illustrate the property that a zero knowledge proof is only convincing to the observer. In other words, the observer would not be able to convince someone else later.

It does so by considering the presence of a coin and a video camera:

Further notice that if Victor chooses his A's and B's by flipping a coin on-camera, this protocol loses its zero-knowledge property; the on-camera coin flip would probably be convincing to any person watching the recording later.

Just like this coin flip, recording Peggy entering side A and leaving through side B would be convincing to any third party aware of the magic door's presence. This would deem it a deterministic proof, rather than a probabilistic proof. This further illustrates Riyil's second point: there is a nonzero probability $P$ such that the prover cheated.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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