The simplest example is the cave of Ali Baba (Ali Baba)

From CryptoWiki
Jump to: navigation, search

A classic example of a protocol with zero-knowledge proof protocol is a proof of knowledge of the password to the door inside a circular cave. Let P knows the password and wants to prove his knowledge of V without disclosing the password itself. Using the following protocol: Here's how the zero-knowledge proof in this case:


  1. V is at point A.
  2. P goes all the way through the cave to the door or down the aisle C, or D. the aisle V does not see which way to go P.
  3. Once P disappears in a cave, V moves to point B.
  4. V asks P, or exit the cave from the left aisle, or the right of passage.
  5. P, if necessary, using the secret to unlock the door, out of the cave from the passage from which asked him to leave V.
  6. P V and repeating steps 1-5 for a number of times .

In the case when P does not know the secret, then it can not deceive V, if the steps of the proof (accreditation) are repeated several times in a row. Since it can only come from the passage in which he went, in every round protocol probability to guess which side of the V will ask him to leave, is 50%. Accordingly, the probability is also deceive V is 50 %. However, the probability to cheat him in two rounds will be over 25 %, and in n rounds, he has only one chance of 2n. V can safely assume that if all n (n = 10-20) rounds proof P are correct, he really knows the secret words that open the door between points C and D.

If V writes everything that happens on video, this video is not evidence for a third party. P and V could agree in advance where V will ask him to leave. Then it will be time to get out of each of the V space, not knowing the magic words. On the other hand, V can spoof video, leaving only successful attempts P, cut out the rest.

It should be noted that the analogy of the cave is not quite correct. Since the proof of knowledge of words P may just go with one hand, while V see which way he went, and out the other. However, it perfectly describes the protocol zero-knowledge proof from a mathematical point of view.[GM89]