La grotte d'Ali Baba

Le concept de divulgation nulle est abstrait. Heureusement, une petite histoire imaginée par les cryptographes Quisquater et Guillou en 1989 le rend limpide : la grotte d'Ali Baba.

Le décor

Imaginez une grotte en forme d'anneau. À l'entrée, le couloir se sépare en deux chemins, un à gauche (A) et un à droite (B), qui se rejoignent au fond. Là, au point de jonction, se trouve une porte magique qui ne s'ouvre qu'en prononçant un mot de passe secret.

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

Peggy affirme connaître le mot de passe. Victor veut en être sûr, mais Peggy refuse de lui dire le mot (ce serait divulguer son secret).

Le protocole, tour par tour

Un tour se déroule ainsi :

1. Engagement : Victor attend à l'entrée, sans regarder. Peggy s'enfonce et choisit au hasard un des deux chemins, A ou B, jusqu'à la porte.
2. Défi : Victor s'avance à l'embranchement et crie au hasard de quel côté il veut voir Peggy ressortir : « Sors par A ! » ou « Sors par B ! ».
3. Réponse : Peggy ressort par le côté demandé.

Point clé : si Victor demande le côté par lequel Peggy est déjà entrée, elle n'a qu'à revenir sur ses pas. Mais s'il demande l'autre côté, elle doit traverser la porte — donc l'ouvrir, donc connaître le mot de passe.

Pourquoi un tricheur échoue

Supposons que Peggy mente et ne connaisse pas le mot de passe.

• Elle entre par un côté au hasard, disons A.
• Si Victor demande A (le côté où elle est), elle s'en sort : elle revient.
• Si Victor demande B, elle est coincée : elle ne peut pas franchir la porte.

Victor choisissant au hasard, le tricheur a exactement 1 chance sur 2 de survivre à un tour.

La force de la répétition

Une chance sur deux, c'est beaucoup trop pour être convaincant. La solution : recommencer. Chaque tour est indépendant, donc les probabilités se multiplient.

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 %

Après 20 tours, un imposteur n'a qu'environ une chance sur un million de passer inaperçu. C'est la consistance (soundness) rendue concrète.

Et la divulgation nulle ?

À aucun moment Victor n'entend le mot de passe. Mieux : il ne peut même pas convaincre un tiers. S'il filmait la scène, un sceptique pourrait toujours dire que Victor et Peggy s'étaient mis d'accord à l'avance sur la suite des côtés demandés. La preuve ne vaut que pour celui qui a lui-même lancé les défis au hasard. Le secret reste donc totalement protégé.

En résumé

• La grotte d'Ali Baba illustre les trois propriétés d'une preuve à divulgation nulle.
• Peggy entre par un côté au hasard ; Victor exige un côté de sortie au hasard ; sans le mot de passe, Peggy ne réussit qu'avec probabilité 1/2 par tour.
• En répétant n tours indépendants, la probabilité de triche tombe à (1/2)^n, donc à quasiment zéro.
• Victor est convaincu sans jamais apprendre le mot de passe.