Prouver sans révéler : ZK et identification

Prouver sans révéler : ZK et identification

Prouver quelque chose consiste d’ordinaire à montrer la pièce justificative : le mot de passe, la carte d’identité, le relevé de compte. Les preuves ZK (Zero-Knowledge, à divulgation nulle de connaissance) cassent ce lien : elles convainquent qu’un énoncé est vrai sans transmettre l’information qui le rend vrai. L’idée, formalisée par Goldwasser, Micali et Rackoff en 1985, va de l’identification par carte à puce jusqu’aux preuves succinctes qui valident des milliers de transactions. Cette fiche en présente les mécanismes, du protocole de Schnorr aux SNARK et STARK, et insiste sur un point que la communication commerciale omet volontiers : une preuve ZK cache le témoin, pas l’utilisateur.

Explication de la marmotte

Montrer au videur d’une salle de concert qu’on a plus de dix-huit ans sans lui laisser lire son nom ni son adresse : voilà l’idée. Il s’agit de convaincre quelqu’un qu’une chose est vraie, sans lui confier le secret qui le démontre. Ce chapitre montre ce que cette idée permet, et aussi ce qu’elle ne cache pas.

→ Lire l’explication complète de la marmotte

Prouver sans donner le secret

Une preuve ZK met en scène un prouveur et un vérificateur autour d’un énoncé public, par exemple « je connais la clé privée associée à cette clé publique ». Le prouveur détient un témoin (witness), ici la clé privée, qui rend l’énoncé vrai. Trois propriétés sont exigées :

• complétude : un prouveur honnête qui détient le témoin convainc toujours un vérificateur honnête ;
• solidité (soundness) : un prouveur qui ne détient pas le témoin échoue, sauf avec une probabilité négligeable ;
• divulgation nulle : le vérificateur n’apprend rien d’autre que la vérité de l’énoncé. Formellement, tout ce qu’il voit pourrait être produit par un simulateur qui ignore le témoin.

Quand la solidité garantit en plus que le prouveur « connaît » le témoin, au sens où on pourrait l’extraire de lui, on parle de preuve de connaissance.

Les usages se rangent en quelques familles. Le mot de passe connu : prouver qu’on connaît un secret sans l’envoyer, ce que font les protocoles d’identification décrits plus bas. L’âge suffisant : prouver que la date de naissance inscrite dans une attestation signée est antérieure à une date seuil, sans révéler la date. L’appartenance : prouver qu’un identifiant figure dans une liste dont seule la racine de Merkle est publiée. Le calcul correct : prouver qu’un programme, exécuté sur des entrées en partie secrètes, a produit un résultat donné.

Dans chaque cas, il faut lister soigneusement ce qui reste public : l’énoncé lui-même, les paramètres, la clé de l’émetteur, l’heure, l’adresse réseau du prouveur, le fait même qu’une preuve a été présentée. Une preuve ZK minimise la divulgation ; elle ne rend pas anonyme.

Protocole interactif

Le protocole de Schnorr (1989) est l’exemple canonique. Dans un groupe d’ordre premier q engendré par g, le prouveur détient x et publie y = gˣ. Il veut prouver qu’il connaît x.

1. Commit : le prouveur tire un aléa r, envoie t = gʳ.
2. Challenge : le vérificateur tire un défi c au hasard et l’envoie.
3. Response : le prouveur renvoie s = r + c·x mod q.
4. Le vérificateur accepte si gˢ = t · yᶜ.

L’égalité tient parce que gʳ⁺ᶜˣ = gʳ · (gˣ)ᶜ. Le triplet (t, c, s) forme le transcript de l’échange.

Pourquoi est-ce solide ? Si un prouveur sait répondre à deux défis différents c₁ et c₂ pour le même engagement t, alors x = (s₁ − s₂) / (c₁ − c₂) mod q : il connaissait donc x. Pourquoi est-ce à divulgation nulle face à un vérificateur honnête ? Parce qu’un simulateur peut choisir s et c au hasard puis calculer t = gˢ · y⁻ᶜ : il fabrique des transcripts valides, de même distribution que les vrais, sans connaître x. Le transcript n’apprend donc rien.

Le même calcul révèle le piège principal : réutiliser r pour deux défis différents livre la clé privée. C’est exactement ce qui est arrivé aux signatures ECDSA (Elliptic Curve Digital Signature Algorithm) d’une console de jeux célèbre en 2010, qui utilisaient un aléa constant.

La transformation de Fiat-Shamir (1986) supprime l’interaction : le défi est remplacé par un condensé, c = H(g, y, t). Le prouveur calcule tout seul et publie (t, s). Comme le condensé dépend de t, il ne peut pas choisir t après avoir vu c. La transformation exige de hacher tout l’énoncé : oublier y ou les paramètres publics dans le calcul de c permet de forger des preuves. Ce défaut, nommé « Fiat-Shamir faible », a été trouvé en 2022 dans plusieurs implémentations de systèmes de preuve, publiées sous le nom de Frozen Heart.

Identification et signatures

Les schémas d’identification à divulgation nulle ont précédé les preuves succinctes de plusieurs décennies. Feige-Fiat-Shamir (1988) repose sur la difficulté d’extraire des racines carrées modulo un nombre composé N dont on ignore la factorisation. Guillou-Quisquater (1988) repose sur l’hypothèse RSA (Rivest-Shamir-Adleman) et réduit le nombre de tours, ce qui le rendait adapté aux cartes à puce de l’époque. Schnorr repose sur le logarithme discret. Les problèmes sous-jacents sont présentés dans Les problèmes difficiles qui rendent la clé publique possible.

La transformation en signature est immédiate : il suffit d’inclure le message dans le condensé, c = H(y, t, m). La signature de Schnorr, et sa descendante EdDSA (Edwards-curve Digital Signature Algorithm), en sont issues. Les hypothèses de sécurité changent alors : la preuve de sécurité de Fiat-Shamir se fait dans le modèle du random oracle (oracle aléatoire), qui traite la fonction de hachage comme une fonction parfaitement aléatoire. Aucune fonction réelle ne l’est, mais aucune attaque pratique n’exploite cet écart pour les schémas classiques correctement instanciés.

La différence entre identification et signature est d’ordre juridique autant que technique. Une identification interactive ne convainc que le vérificateur présent : il ne peut pas montrer le transcript à un tiers comme preuve, puisqu’il aurait pu le simuler lui-même. Une signature, au contraire, est transférable et vérifiable par tous ; voir Signer numériquement : preuve publique, politiques de vérification.

Reste le rejeu. Une identification interactive y résiste, car chaque défi est neuf. Une preuve non interactive, elle, se recopie : si elle ne lie aucun contexte, quiconque l’intercepte peut la présenter à nouveau. Il faut donc inclure dans le condensé un nonce fourni par le vérificateur, un identifiant de session ou une date, comme le font les protocoles d’authentification décrits dans Authentifier les personnes et les services.

SNARK et STARK

Pour prouver des énoncés arbitraires, on les traduit en circuit arithmétique sur un corps fini, puis en système de contraintes : chaque porte devient une équation que les valeurs des fils doivent satisfaire. Les variables se répartissent en entrées publiques (connues du vérificateur) et privées (le témoin).

Un SNARK (Succinct Non-interactive ARgument of Knowledge) produit une preuve succincte, courte et rapidement vérifiée quelle que soit la taille du calcul. Groth16 (2016) donne des preuves de trois éléments de groupe, de l’ordre de 128 à 256 octets selon l’encodage, vérifiées en quelques millisecondes. En échange, il exige un trusted setup (mise en place de confiance) propre à chaque circuit : une cérémonie génère des paramètres publics à partir d’un secret qui doit être détruit, surnommé « déchet toxique ». Quiconque le conserve peut forger des preuves de faux énoncés, sans que rien ne le trahisse. Les cérémonies multipartites atténuent le risque : les paramètres sont sûrs si au moins un participant a détruit sa contribution. Des systèmes comme PLONK (2019) utilisent un setup universel, réutilisable pour tous les circuits jusqu’à une taille donnée.

Un STARK (Scalable Transparent ARgument of Knowledge) supprime le setup : c’est la transparence, dans laquelle tous les paramètres sont publics et aléatoires. Il ne repose que sur des fonctions de hachage, ce qui le rend plausiblement résistant aux ordinateurs quantiques. Le prix est la taille : ses preuves pèsent typiquement des dizaines à des centaines de kilo-octets.

Le coût de génération est la contrainte dominante pour les deux familles. Le temps de preuve croît avec le nombre de contraintes, et certaines opérations coûtent très cher en circuit. Un seul bloc de compression SHA-256 (Secure Hash Algorithm, 256 bits) représente plusieurs dizaines de milliers de contraintes, tandis qu’une fonction de hachage conçue pour les circuits, comme Poseidon, en demande quelques centaines. Prouver l’appartenance à un arbre de Merkle de profondeur 20 hache vingt fois : le choix de la fonction change le temps de preuve de plusieurs ordres de grandeur. Les usages dans les chaînes de blocs sont développés dans Chaînes de blocs, wallets et cryptographie économique.

Exemples et ateliers

Preuve de Schnorr jouet. Avec p = 23, le sous-groupe d’ordre q = 11 engendré par g = 2 (car 2¹¹ = 2 048 ≡ 1 mod 23) :

secret x = 6           public y = 2⁶ mod 23 = 18
commit  r = 4          t = 2⁴ mod 23 = 16
défi    c = 5
réponse s = 4 + 5·6 mod 11 = 1
vérif.  gˢ = 2         t·yᶜ = 16 · 18⁵ mod 23 = 16 · 3 mod 23 = 2   accepté

Si le prouveur réutilise r = 4 pour un défi c = 2, il répond s = 16 mod 11 = 5. Le vérificateur calcule alors (1 − 5) / (5 − 2) mod 11 = −4 · 3⁻¹ = 7 · 4 = 28 mod 11 = 6 : la clé privée est retrouvée. Ces tailles sont évidemment pédagogiques ; en pratique q fait au moins 256 bits.

Rendre la preuve publiable. On remplace c = 5 par c = H(g, y, t, contexte) mod q, où contexte contient le nom du service et un nonce de session. La preuve publiée est (t, s) ; chacun recalcule c et vérifie. Sans le contexte, la preuve serait rejouable ailleurs.

Preuve d’inclusion Merkle en ZK. Énoncé : « je connais une feuille et un chemin qui mènent à la racine publique R ». Entrées publiques : R, et un identifiant d’usage dérivé de la feuille et du contexte (souvent appelé nullifier), qui empêche de présenter deux fois la même appartenance sans révéler laquelle. Entrées privées : la feuille, les condensés frères et les bits de position. Le circuit recalcule la racine et la compare à R.

Données d’une preuve d’âge.

Public	Privé
Seuil (18 ans) et date de référence	Date de naissance
Clé publique de l’émetteur	Signature de l’émetteur sur l’attestation
Nonce du vérificateur	Autres attributs (nom, adresse)
Résultat : vrai	Identifiant de l’attestation

La date de référence doit venir du vérificateur ou d’une source fiable : si le prouveur la choisit, il prouve un énoncé inutile. Restent visibles malgré la preuve : l’émetteur, l’heure, l’adresse IP (Internet Protocol) et l’empreinte du navigateur.

Pièges classiques

Croire que ZK masque toutes les métadonnées : il masque le témoin, rien d’autre. Prouver le mauvais énoncé, par exemple « je possède une attestation valide » sans lier l’attestation à son porteur, ce qui autorise le prêt. Oublier le coût du circuit, découvert quand la génération prend une minute sur un téléphone. Mal choisir les paramètres publics, ou ne pas tous les inclure dans le condensé de Fiat-Shamir. Gouverner un trusted setup sans transparence, avec un seul participant ou sans trace publique de la cérémonie.

À ne pas confondre

Le ZK n’est pas du chiffrement : il n’y a rien à déchiffrer, seulement un énoncé dont la vérité se contrôle. L’identification ZK convainc un vérificateur présent ; la signature convainc tout le monde, durablement. Un SNARK est court mais demande souvent un setup de confiance ; un STARK est transparent mais volumineux. L’anonymat cache qui agit ; la minimisation de divulgation limite ce qui est révélé, et l’identité peut en faire partie.

FAQ

Une preuve ZK rend-elle un utilisateur anonyme ?
Non. Elle évite de révéler le témoin. L’identité peut rester visible par le canal, l’émetteur de l’attestation ou la corrélation des usages.

Pourquoi le défi doit-il être imprévisible ?
Parce qu’un prouveur qui connaît le défi à l’avance peut appliquer la méthode du simulateur et produire un transcript valide sans connaître le secret.

Conclusion

Les preuves à divulgation nulle séparent enfin « convaincre » de « montrer ». Le schéma engagement, défi, réponse, rendu non interactif par Fiat-Shamir, fonde les signatures modernes ; les circuits de contraintes étendent l’idée à des calculs entiers, au prix d’un coût de génération élevé et parfois d’une cérémonie de confiance. Bien employées, elles minimisent la divulgation. Elles ne dispensent ni de choisir le bon énoncé, ni de protéger les métadonnées, ce qui laisse encore un peu de travail aux humains.

🐝 Ce qui arrive si on s’en passe

Sans preuve à divulgation nulle, prouver revient à montrer : pour attester un âge, une pièce d’identité complète est transmise, et chaque vérificateur en conserve une copie qui devient à son tour un point de fuite, bien au-delà de la seule réponse « majeur ou non » dont il avait besoin. Pour s’identifier, le secret lui-même circule, si bien qu’un faux vérificateur ou un serveur compromis le recueille et le rejoue à volonté. Chaque contrôle ajoute ainsi un dépositaire de plus à une information qui n’aurait jamais dû quitter son propriétaire, et la ruche distribue son plan à chaque visiteur qui demande à voir la porte.

🦫 Explication de la marmotte 🍫

Une preuve à divulgation nulle de connaissance met en jeu deux rôles : le prouveur, qui connaît un secret appelé témoin, et le vérificateur, qui veut être convaincu qu’un énoncé est vrai. Trois propriétés sont attendues : un prouveur honnête convainc toujours, c’est la complétude ; un tricheur échoue presque toujours, c’est la solidité ; et le vérificateur n’apprend rien d’autre que la vérité de l’énoncé. Dans la version interactive, le prouveur s’engage d’abord sur une valeur tirée au hasard, le vérificateur lui envoie un défi imprévisible, puis le prouveur répond d’une façon qui n’est possible que s’il connaît le secret. Le protocole de Schnorr, qui prouve qu’on connaît une clé privée, suit ce schéma. La transformation de Fiat-Shamir remplace le défi du vérificateur par une empreinte calculée sur l’échange, ce qui donne une preuve publiable sans dialogue, et même une signature. Pour des énoncés plus complexes, comme « ce calcul est correct » ou « cette personne figure dans la liste », on traduit le problème en un circuit de contraintes. Les preuves courtes appelées SNARK peuvent exiger une préparation initiale dont il faut garantir l’honnêteté ; les STARK, une autre famille, s’en passent. Ces preuves coûtent cher à produire, et elles ne cachent que le secret : l’heure, l’adresse réseau ou l’identité du vérificateur restent visibles, et prouver un énoncé mal choisi ne protège rien.

À lire aussi

• Calculer, engager et anonymiser avec des primitives spécialiséesRegrouper les primitives avancées qui protègent des calculs, des engagements ou des identités, tout en exposant leurs coûts et leurs fuites résiduelles.
• Hachage dans les systèmes: intégrité, arbres et preuvesRegrouper les usages systémiques du hachage: empreintes, arbres, preuves, déduplication, chaînes d’intégrité et limites de sécurité.
• Équité, vote, contrats et divulgation contrôléeConserver les protocoles avancés classiques en les réorganisant autour des problèmes d’équité, de décision collective et de divulgation contrôlée.

Pages voisines

La citent

• Calculer, engager et anonymiser avec des primitives spécialisées
• Équité, vote, contrats et divulgation contrôlée
• Hachage dans les systèmes: intégrité, arbres et preuves

Prouver sans révéler : ZK et identification

Elle cite

• ⇄Lien dans les deux sens :Chaînes de blocs, wallets et cryptographie économique
• Les problèmes difficiles qui rendent la clé publique possible
• Signer numériquement : preuve publique, politiques de vérification
• Authentification défi-réponse, rejeu, relais et attaque hors ligne
• Authentifier les personnes et les services
• Informatique quantique : histoire, acteurs, usages et avenir

⇄ : les deux pages se citent l’une l’autre.