zero knowledge proof and its protocol

Question

In Zero-Knowledge Proof where we take the analogy of Peggy (Prover) and Victor (Verifier):

In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a circle, with the entrance on one side and the magic door blocking the opposite side. Victor says he'll pay her for the secret, but not until he's sure that she really knows it. Peggy says she'll tell him the secret, but not until she receives the money. They devise a scheme by which Peggy can prove that she knows the word without telling it to Victor.

First, Victor waits outside the cave as Peggy goes in. They label the left and right paths from the entrance A and B. Peggy randomly takes either path A or B. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path. Note that Victor does not know which path she has gone down.

However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path that she had entered by. Since Victor would choose A or B at random, he would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests would become vanishingly small. Thus, if Peggy reliably appears at the exit Victor names, he can conclude that she is very likely to know the secret word.

The following method of verification is convincing enough for me:

1. Victor goes through both corridors A and B and assures himself that there is no way one could go to the other end.(Since Victor has no knowledge of secret, he is convinced himself this is true).

2. He could go to entrance of corridor A, ask Peggy to go through entrance B and come from the end of A. (Peggy does, and comes out of end of A)

3. Victor would also proceed the other way where he stands at entrance of B and ask Peggy to come though end of B after going through A.

4. If Peggy could do both 2 and 3, Victor is convinced that Peggy knows the secret.

I feel that this method is wrong and wonder why. So, why would classical method be preferred over this? What are the weaknesses of this method?

Answer 1

The problem is that the cave analogy cannot be pushed that far. There's a discussion on that exact question, take a look. The "zero knowledge" part requires that the proof cannot be distinguished from a simulation by a cheating verifier.

Answer 2

The discussion on Wikipedia linked to by Kerrek SB is close but maybe not quite clear.

Let's say that Peggy manages to convince Victor that she knows the secret. Can Victor convince you that Peggy knows the secret? In a zero-knowledge proof, the answer should be no. Victor not only gains "zero" knowledge about the secret itself, but also no transferrable knowledge about who knows the secret.

As mentioned in the link, consider the scenario where Victor videotapes the session for you. In the first protocol, the video tape could be faked simply by having Victor and Peggy agree on the "random" challenges Victor will give to Peggy ahead of time. Since you have no way of knowing whether Victor told Peggy the challenges or not, the videotape is actually worthless and does not convince you of anything.

However in your modified protocol, a videotape would be convincing. Therefore it leaks more than "zero" knowledge. Now having the ability to transfer knowledge is not always bad! In some applications, you want to use something that is zero knowledge in all respects except that you can transfer knowledge (these are called non-interactive zero knowledge proofs).

The comments on Wikipedia then go into dealing with a verifier that is dishonest (that is if Victor can prove that he generated his challenge after Peggy is already in one of the paths, maybe by flipping the coin on video) and maintaining zero-knowledge with rewindable blackbox access to the verifier (which is where the analogy breaks down somewhat). However it is not necessary to consider the dishonest case to distinguish between the two protocols in the original post.

Answer 3

Taking the analogy that far is simple, he doesn't know which path has the magic door and what the password is. Oh, and he is only allowed to take one path all the way to the end. So he can't get through yet.

Okay, it's a stretch on the analogy, the one I heard, there are two magic doors and Alice knows the pass to both which have different passwords, this is closer to the actual algorithm, and makes the analogy make a lot more sense. This of course, gives me an idea for a crystal maze puzzle where they fundamentally have to solve it with this analogy.