Interactive challenge-response protocols

The Ali Baba cave is not a curiosity: it follows a general pattern common to almost all interactive zero-knowledge protocols, the three-step challenge-response scheme.

The three steps

Every interactive protocol of this kind unfolds in three messages, in this order.

   PROUVEUR (Peggy)                     VERIFIEUR (Victor)
        |                                     |
        |  1. ENGAGEMENT  ------------------> |
        |     (Peggy se "verrouille"          |
        |      sur un choix, sans le montrer) |
        |                                     |
        |  2. <----------------- DEFI         |
        |        (Victor tire une             |
        |         question AU HASARD)         |
        |                                     |
        |  3. REPONSE  ---------------------> |
        |     (Peggy repond ; elle ne peut    |
        |      reussir que si elle sait)      |
        |                                     |

1. Commitment: the prover fixes a choice or a value and commits to it without revealing it. In the cave, this is entering through a specific path.
2. Challenge: the verifier sends a question drawn at random. In the cave, this is the required exit side.
3. Response: the prover answers consistently with their commitment. They can satisfy all the possible questions only if they genuinely know the secret.

Why the challenge must be random

This is the most important point, and the most often misunderstood.

If the verifier always asked the same question, or a predictable question, the prover could prepare their answer in advance — even without knowing the secret. In the cave: if Peggy knew that Victor would always ask "come out through A", she would always enter through A and would never need the door.

The randomness of the challenge is therefore what traps the cheater: since they cannot guess the question, they must be ready to answer all possible questions, which only knowledge of the secret allows.

If the challenge is…	Then…
predictable	the cheater prepares their answer and gets through: the protocol is broken
random	the cheater has to guess; they have only a small chance per round

Why a single round is not enough

With a binary challenge (two possible questions), a cheater gets through a round with probability 1/2. That is huge. So a single round proves almost nothing.

Soundness comes only with repetition: each additional round multiplies the difficulty for the cheater. With k possible questions per round and n rounds, the probability of cheating is:

    (1 / k)^n

We repeat until this number is negligible — small enough that luck can reasonably be ruled out.

In summary

• Interactive protocols follow the commitment -> challenge -> response scheme.
• The randomness of the challenge is crucial: a predictable challenge would let the cheater prepare their answer without knowing the secret.
• A single round is not enough; we repeat until the probability of cheating (1/k)^n is negligible. This is what ensures soundness.