Prouver qu’on connaît un secret sans le dire
Une preuve à divulgation nulle de connaissance permet de convaincre quelqu’un que vous connaissez un secret, sans montrer ce secret. Elle sert à se connecter sans envoyer de mot de passe et à prouver des faits sur des données privées.
Aujourd’hui, vous jouez à un jeu qui montre l’idée, puis vous mesurez pourquoi il fonctionne.
À la fin de cette leçon
Remarque
Je peux expliquer la complétude, la correction et la divulgation nulle à l’aide d’une preuve interactive.
Mots-clés
| Mot | Ce que ça veut dire |
|---|---|
| Prouveur | celui qui affirme connaître un secret |
| Vérificateur | celui qui contrôle l’affirmation |
| Défi | une question tirée au hasard par le vérificateur |
| Complétude | un prouveur honnête réussit toujours |
| Correction | un prouveur qui triche échoue presque toujours |
| Divulgation nulle | le vérificateur n’apprend rien, sauf que l’affirmation est vraie |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La caverne, une preuve interactive
Une caverne a deux chemins, A et B, reliés au fond par une porte fermée à clé. Le prouveur dit qu’il connaît le mot qui ouvre la porte.
Le prouveur entre par un chemin pendant que le vérificateur attend dehors. Puis le vérificateur crie un chemin au hasard, A ou B. Le prouveur doit sortir par ce chemin. Avec le mot, il y arrive toujours. Sans le mot, il ne réussit que s’il a deviné juste, une fois sur deux.
Jouer de nombreuses fois à la caverne
docker exec jupyter python3 steps/cave.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.
Lire ce que le labo a affiché
Le labo écrit en anglais : « rounds » veut dire tours et « cheaters » tricheurs. Le prouveur qui connaît le mot a réussi 20 tours sur 20. C’est la complétude.
Ensuite, 1000 tricheurs ont joué. Après le tour 1, il en restait 493, après le tour 2 seulement 243, et après le tour 10 aucun. Chaque tour les divise à peu près par deux. Vingt tours laissent à un tricheur une chance sur 1048576. C’est la correction.
Exemple travaillé : la chance d’un tricheur
| Tours | Chance de tous les réussir en trichant | En nombre décimal |
|---|---|---|
| 1 | 1 sur 2 | 0,5 |
| 2 | 1 sur 4 | 0,25 |
| 3 | 1 sur 8 | 0,125 |
| 10 | 1 sur 1024 | environ 0,001 |
| 20 | 1 sur 1048576 | environ 0,000001 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À vous : un tricheur dans la caverne
import random
rng = random.Random(3)
def un_tour(connait_le_mot):
entre_par = rng.choice("AB")
demande = rng.choice("AB")
if connait_le_mot:
return True
return entre_par == demande
reussis = 0
for n in range(10):
if un_tour(False):
reussis = reussis + 1
else:
print("pris au tour", n + 1)
break
print("tours réussis :", reussis)
# Remplacez False par True, pour que le prouveur connaisse le mot, et relancez.
Pourquoi le vérificateur n’apprend rien
Si vous regardez de dehors, vous voyez le prouveur sortir par le chemin demandé. Vous n’entendez jamais le mot.
Pire pour un espion : un film du jeu ne prouve rien. Les deux personnes ont pu convenir des chemins à l’avance et couper le film. Si un faux enregistrement ressemble en tout à un vrai, le vrai ne dévoile rien. C’est l’idée de la divulgation nulle.
Erreur fréquente
Attention
On croit souvent que divulgation nulle veut dire que le vérificateur n’apprend rien du tout. Il apprend une chose : que l’affirmation est vraie. Ce qu’il n’apprend pas, c’est le secret, ni rien qui l’aide à le trouver.
Lister les scripts du labo
docker exec jupyter ls stepsAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.