Zero-Knowledge Proof

Objectif : prouver la connaissance d’un secret sans le révéler.

Exemple — 3-coloration de graphe

• Le prouveur s’engage sur un coloriage aléatoirement permuté
• Le vérifieur contrôle localement la validité sans apprendre le coloriage global

Preuve de Schnorr

Objectif : prouver la connaissance de $x$ tel que :

$$y=g^x\mathrm{mod}p$$

Protocole

1. $P\to V$ : $t=g^r$
2. $V\to P$ : défi $c$
3. $P\to V$ : $s=r+cx$

Vérification

$$g^s=t\cdot y^c$$