The Ali Baba cave

The concept of zero-knowledge is abstract. Fortunately, a little story devised by the cryptographers Quisquater and Guillou in 1989 makes it crystal clear: the Ali Baba cave.

The setting

Imagine a cave shaped like a ring. At the entrance, the corridor splits into two paths, one on the left (A) and one on the right (B), which meet at the far end. There, at the junction point, is a magic door that opens only when a secret password is spoken.

              PORTE MAGIQUE
                  (fond)
                   ||
          +--------++--------+
          |                  |
     chemin A            chemin B
          |                  |
          +--------++--------+
                   ||
                ENTREE
                   |
                 Victor

Peggy claims to know the password. Victor wants to be sure, but Peggy refuses to tell him the word (that would disclose her secret).

The protocol, round by round

A round proceeds as follows:

1. Commitment: Victor waits at the entrance, without looking. Peggy heads in and chooses at random one of the two paths, A or B, up to the door.
2. Challenge: Victor steps up to the fork and shouts at random which side he wants to see Peggy come out of: "Come out through A!" or "Come out through B!".
3. Response: Peggy comes out through the requested side.

Key point: if Victor asks for the side by which Peggy already entered, she just has to retrace her steps. But if he asks for the other side, she must go through the door — so open it, so know the password.

Why a cheater fails

Suppose Peggy is lying and does not know the password.

• She enters through a side at random, say A.
• If Victor asks for A (the side she is on), she gets away with it: she comes back.
• If Victor asks for B, she is stuck: she cannot get through the door.

Since Victor chooses at random, the cheater has exactly a 1 in 2 chance of surviving a round.

The power of repetition

One chance in two is far too much to be convincing. The solution: start over. Each round is independent, so the probabilities multiply.

Probabilite qu'un tricheur reussisse n tours d'affilee :

    (1/2)^n

  n = 1  ->  1/2       = 50 %
  n = 2  ->  1/4       = 25 %
  n = 5  ->  1/32      = 3 %
  n = 10 ->  1/1024    = 0,1 %
  n = 20 ->  1/1048576 = 0,0001 %

After 20 rounds, an impostor has only about a one-in-a-million chance of going unnoticed. This is soundness made concrete.

And zero-knowledge?

At no point does Victor hear the password. Better still: he cannot even convince a third party. If he filmed the scene, a skeptic could always say that Victor and Peggy had agreed in advance on the sequence of requested sides. The proof is worth something only to the person who themselves issued the challenges at random. So the secret remains completely protected.

In summary

• The Ali Baba cave illustrates the three properties of a zero-knowledge proof.
• Peggy enters through a side at random; Victor demands an exit side at random; without the password, Peggy succeeds only with probability 1/2 per round.
• By repeating n independent rounds, the probability of cheating drops to (1/2)^n, hence to almost zero.
• Victor is convinced without ever learning the password.