Protocoles interactifs défi-réponse

La grotte d'Ali Baba n'est pas une bizarrerie : elle suit un patron général commun à presque tous les protocoles à divulgation nulle interactifs, le schéma défi-réponse en trois temps.

Les trois étapes

Tout protocole interactif de ce type se déroule en trois messages, dans cet ordre.

   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. Engagement (commitment) : le prouveur fixe un choix ou une valeur et s'y engage sans la dévoiler. Dans la grotte, c'est le fait d'entrer par un chemin précis.
2. Défi (challenge) : le vérifieur envoie une question tirée au hasard. Dans la grotte, c'est le côté de sortie exigé.
3. Réponse (response) : le prouveur répond de façon cohérente avec son engagement. Il ne peut satisfaire toutes les questions possibles que s'il connaît réellement le secret.

Pourquoi le défi doit être aléatoire

C'est le point le plus important, et le plus souvent mal compris.

Si le vérifieur posait toujours la même question, ou une question prévisible, le prouveur pourrait préparer sa réponse à l'avance — même sans connaître le secret. Dans la grotte : si Peggy savait que Victor demanderait toujours « sors par A », elle entrerait toujours par A et n'aurait jamais besoin de la porte.

L'aléa du défi est donc ce qui piège le tricheur : comme il ne peut pas deviner la question, il doit être prêt à répondre à toutes les questions possibles, ce que seule la connaissance du secret permet.

Si le défi est…	Alors…
prévisible	le tricheur prépare sa réponse et passe : le protocole est cassé
aléatoire	le tricheur doit deviner ; il n'a qu'une faible chance par tour

Pourquoi un seul tour ne suffit pas

Avec un défi binaire (deux questions possibles), un tricheur passe un tour avec probabilité 1/2. C'est énorme. Un unique tour ne prouve donc presque rien.

La solidité (soundness) ne vient qu'avec la répétition : chaque tour supplémentaire multiplie la difficulté pour le tricheur. Avec k questions possibles par tour et n tours, la probabilité de triche vaut :

    (1 / k)^n

On répète jusqu'à ce que ce nombre soit négligeable — assez petit pour qu'on puisse raisonnablement exclure la chance.

En résumé

• Les protocoles interactifs suivent le schéma engagement -> défi -> réponse.
• Le caractère aléatoire du défi est crucial : un défi prévisible permettrait au tricheur de préparer sa réponse sans connaître le secret.
• Un seul tour ne suffit pas ; on répète jusqu'à rendre la probabilité de triche (1/k)^n négligeable. C'est ce qui assure la consistance/solidité.