Comment prouver que l’on connaît un secret sans le révéler ?

Un code secret est constitué d’un unique chiffre compris entre $0$ et $9$. Alice et Bernard sont tous deux censés connaître ce code, mais ils ne se sont jamais rencontrés. Alice doit donc prouver à Bernard qu’elle connaît le code sans le lui révéler.

Pour cela, ils utilisent une boîte contenant $10$ cases numérotées de $0$ à $9$. Chaque case possède une serrure avec deux clés : une pour Alice et une pour Bernard.

Sans qu’Alice puisse le voir, Bernard conserve la clé correspondant au code secret et jette toutes les autres. Si Bernard est un usurpateur et ne connaît pas le code, il choisit uniformément au hasard l’une des $10$ clés.

Indépendamment, et sans que Bernard puisse la voir, Alice place un jeton dans la case correspondant au code secret. Si Alice est une usurpatrice et ne connaît pas le code, elle choisit uniformément au hasard l’une des $10$ cases.

Bernard ouvre ensuite l’unique case dont il a conservé la clé. Si le jeton d’Alice s’y trouve, la tentative d’identification est considérée comme réussie.

On suppose que la probabilité que Bernard soit un usurpateur est $5\%$.

1. On suppose qu’Alice connaît le code secret. On note
   $$C=\{\text{Bernard a conservé la clé correspondant au code secret}\}$$et
   $$U=\{\text{Bernard est un usurpateur}\}.$$

   1. Calculer
      $$\mathbb{P}(C\mid U).$$

   2. Calculer
      $$\mathbb{P}(U\cap C).$$

   3. Calculer
      $$\mathbb{P}(U\mid C).$$

2. On suppose maintenant qu’Alice et Bernard sont tous les deux des usurpateurs. Quelle est la probabilité qu’Alice place le jeton dans la case correspondant au véritable code et que Bernard conserve la clé correspondant au véritable code ?

3. Toujours en supposant qu’Alice et Bernard sont tous les deux des usurpateurs, quelle est la probabilité que Bernard conserve la clé correspondant à la case dans laquelle Alice a placé le jeton ?

4. Le code secret est maintenant constitué de $4$ chiffres, et le protocole est répété indépendamment pour chacun des chiffres. On suppose qu’Alice connaît le code mais que Bernard est un usurpateur. Quelle est la probabilité que Bernard choisisse la bonne clé lors des quatre étapes ?

Remarque : Ce type de méthode est appelé protocole à divulgation nulle de connaissance (zero-knowledge protocol). De tels protocoles sont utilisés dans des systèmes d’authentification cryptographique car ils permettent à une personne de prouver qu’elle connaît un secret sans avoir à le révéler. Ils jouent un rôle important dans les technologies visant à préserver la confidentialité, notamment dans certains systèmes liés aux cryptomonnaies comme Bitcoin.