# Preuve à divulgation nulle de connaissance

Une preuve à divulgation nulle de connaissance (Zero Knowledge Interactive proof ou ZKIP en anglais) est un protocole cryptographique permettant l'authentification sécurisée d'informations. Dans le cadre de ce protocole, une entité, nommée « fournisseur de preuve » ou prouveur peut démontrer à une autre partie, appelée le vérificateur, qu'une déclaration est vraie, sans révéler aucune information supplémentaire à son sujet. Ces preuves jouent un rôle essentiel dans la garantie de la confidentialité et de la sécurité de divers systèmes cryptographiques modernes.
En pratique, ces schémas se présentent souvent sous la forme de protocoles de type « défi/réponse » (challenge-response). Le vérificateur et le fournisseur de preuve s'échangent des informations et le vérificateur contrôle si la réponse finale est positive ou négative. Il existe également des variantes sans interaction (non-interactive zero-knowledge proof) qui peuvent-être construites dans le modèle de l'oracle aléatoire par l'heuristique de Fiat-Shamir.
Les preuves à divulgation nulle reposent sur trois propriétés fondamentales :
* Complétude : Si la déclaration est vraie et que le prouveur suit le protocole, le vérificateur sera convaincu.
* Robustesse : Si la déclaration est fausse, un prouveur malveillant ne pourra pas convaincre un vérificateur honnête.
* Zéro-connaissance : Le vérificateur n'acquiert aucune information supplémentaire sur la déclaration, au-delà de sa véracité.
Les ZKP peuvent être utilisées pour cacher des informations dans un registre distribué (comme une blockchain), tout en permettant la validation de ces informations. Cela est particulièrement utile dans des systèmes où les parties n'ont pas totalement confiance les unes envers les autres, tout en évitant la nécessité d'une tierce partie de confiance.

## Définition formelle des preuves à divulgation nulle

Nous pouvons utiliser la notion de relation en mathématique pour définir les preuves à divulgation nulle de connaissance un peu plus rigoureusement. Ces preuves permettent à un prouveur P de convaincre un vérificateur V qu'il connaît un témoin w lié à une déclaration x telle que (x,w) ∈ R, où R est une relation bien définie. Un exemple classique est la preuve de connaissance d’un logarithme discret. Un problème difficile peut donc être vu comme une relation R dite difficile : Il existe un algorithme efficace pour générer des paires (x,w)∈R et il est difficile (infaisable) de déterminer w connaissant uniquement x.

## Exemples
### La grotte d'Ali Baba

Jean-Jacques Quisquater et Louis Guillou publient en 1989 un article intitulé « How to explain zero-knowledge protocols to your children » (ou « Comment expliquer à vos enfants les protocoles sans apport de connaissance » ). On y trouve une introduction pédagogique à la notion de preuve à divulgation nulle de connaissance, basée sur le conte « Ali Baba et les quarante voleurs ». On considère deux personnes : Peggy (prouveur) et Victor (vérificateur). On considère aussi une grotte avec une bifurcation : A et B. On peut passer de A à B ou de B à A en ouvrant une porte à l'aide d'un mot magique. Peggy veut prouver à Victor qu'elle connaît le mot magique pour ouvrir la porte mais ne veut pas que Victor l'apprenne. Il s'agit d'une « preuve de connaissance » (Peggy prouve à Victor qu'elle connaît la clé) mais sans « apport d'information » (Peggy conserve son secret). Pour ce faire, Peggy et Victor vont répéter plusieurs fois le scénario suivant.
* Engagement. Victor (en vert) attend à l'entrée de la caverne et ne voit pas l'intérieur du tunnel. Peggy (en violet) s'introduit dans la galerie et choisit aléatoirement le cul-de-sac à gauche ou à droite, par exemple en lançant un dé ou une pièce de monnaie.
* Défi. Victor entre dans le tunnel et attend à la bifurcation. Il lance une pièce de monnaie. Selon le côté sur lequel tombe la pièce, Victor crie « A » ou « B ».
* Réponse. Peggy doit prouver maintenant qu'elle est en possession de la preuve, elle doit apparaître vers la sortie demandée par Victor.
Plusieurs cas de figure se présentent :
* Peggy connaît le mot magique :
** si elle se trouve en A et que Victor dit « A », elle satisfait la requête
** si elle se trouve en B et que Victor dit « B », elle satisfait la requête
** si elle se trouve en A et que Victor dit « B », elle satisfait la requête en passant de A à B avec le mot magique
** si elle se trouve en B et que Victor dit « A », elle satisfait la requête en passant de B à A avec le mot magique
* Peggy ne connaît pas le mot magique :
** si elle se trouve en A et que Victor dit « B », elle ne satisfait pas la requête
** si elle se trouve en B et que Victor dit « A », elle ne satisfait pas la requête
** si elle se trouve en A et que Victor dit « A », elle satisfait la requête
** si elle se trouve en B et que Victor dit « B », elle satisfait la requête
Si Peggy ne connaît pas le mot magique, il se peut que Victor soit induit en erreur dans les cas où sa requête correspond à la position actuelle de Peggy. En partant du principe qu'elle suit le protocole (critère de consistance), une erreur de Peggy sera considérée comme une preuve de non-connaissance. Victor peut de suite arrêter, il est assuré que Peggy ne connaît pas le mot magique.
En recommençant plusieurs fois à partir de la première étape, Victor peut collecter suffisamment d'informations pour être quasiment sûr que Peggy est en possession du mot magique. À chaque nouvel essai, il améliore son assurance. Si Peggy n'est pas en possession du mot magique, il y a 50 % de chance pour qu'elle commette une erreur. Avec N essais, la probabilité pour que Victor affirme que Peggy possède le secret alors qu'elle ne le possède pas est de ${\frac {1}{2^{N}}}~$.
Pour mettre ceci en parallèle avec des primitives cryptographiques dans le cadre d'un protocole « stimulation/réponse », il y a toujours une chance, aussi infime soit-elle, que la réponse donnée par le fournisseur de preuve soit tirée au hasard et qu'elle corresponde à ce qui était attendu par le vérificateur.

### Le daltonien et les boules colorées

Dans cet exemple, on considère deux objets identiques, ayant cependant une caractéristique qui les différencie, ainsi deux boules semblables, mais de couleurs différentes. L'exemple provient de Oded Goldreich, qui utilisa deux cartes de deux couleurs différentes.
L’exemple se fonde sur une situation fictive où deux personnes interviennent : l'une est daltonienne et l'autre distingue les couleurs. Il y a deux boules indistinguables hors les couleurs, rouge et verte. Pour la daltonienne, elles sont parfaitement identiques. L'objectif est de prouver à la daltonienne que la personne qui voit les couleurs est capable de distinguer les boules grâce à leurs couleurs, mais sans que jamais leurs couleurs (rouge ou verte) soient révélées.
La personne daltonienne place les boules derrière son dos, puis prend une des boules et la montre à l’autre personne. Elle la remet dans son dos puis choisit de montrer une des boules, soit la même, soit l'autre avec une probabilité de 50 %. Elle demande alors « ai-je changé de boule ? ». Le processus est répété autant de fois qu'il le faut. Si le protocole est répété suffisamment de fois et si la personne non daltonienne donne toujours la bonne réponse, la personne daltonienne sera convaincue avec une très forte probabilité que son partenaire est effectivement capable de distinguer les boules par leur couleur. C'est un protocole de preuve à divulgation nulle de connaissance puisqu’il ne révèle jamais la couleur des boules.

### La grille de Sudoku

Dans cet exemple, Peggy veut prouver à Victor qu'elle connaît la solution d'une grille standard de Sudoku.
Pour cela, après avoir résolu la grille de Sudoku elle découpe sa grille soigneusement aux ciseaux. Elle se retrouve donc avec 81 petits carrés de papier sur lesquels sont écrits les chiffres de la grille de sudoku résolue. Elle retourne tous les bouts de papier face cachée. Sauf les chiffres de départ de la grille (ceux présents avant d'avoir commencé à résoudre la grille). La procédure de la preuve peut commencer.
Victor peut alors choisir n'importe quelle ligne, colonne, ou carré 3x3. Peggy prend les 9 carrés de papier correspondants, les mélange soigneusement, et les donne à Victor. Victor peut alors vérifier qu'il y a bien les chiffres de 1 à 9. Ensuite, Peggy remet les petits carrés à leur place face cachée sur la grille. Victor répète la procédure jusqu’à avoir vérifié les 9 lignes, 9 colonnes, et les 9 carrés 3x3 de la grille de Sudoku.
À la fin de la procédure, Victor a la preuve que Peggy a la solution de la grille de Sudoku sans la connaître.

### Code secret à vérifier à l'aide d'un tiers

Dans cet exemple, Peggy et Victor veulent s'assurer qu'ils possèdent chacun un même code secret sans pour autant le révéler. On peut imaginer une situation dans laquelle deux agents doivent se rencontrer et confirmer leur identité à l'aide d'un code unique qui leur a été préalablement transmis parallèlement.
Imaginons que Victor connaît le code (ex. 314 091) et souhaite vérifier que Peggy possède le même sans que l'un ou l'autre le révèle. La présence d'une tierce personne de confiance, Camille, permet de vérifier, à l'aide de la méthode suivante :
* Camille choisit un nombre secret (ex. 123 123) et le chuchotte à Peggy
* Peggy ajoute le nombre secret à son propre code secret, puis chuchotte le résultat à Victor
* Victor soustrait son code secret au résultat qu'il a reçu, puis le chuchotte à Camille
Si les codes de Peggy et Victor sont identiques, Camille doit alors recevoir le nombre secret choisi au départ (123 123). Ainsi Camille peut affirmer si les codes de Victor et de Peggy sont identiques, sans pour autant le connaître : en effet, le code 314 091 n'est explicitement transmis dans aucun échange. Cette méthode permet aux personnages présents de prouver l'unicité du code secret sans le divulguer tout au long du test.

## D'autres exemples pratiques

Parmi les preuves cryptographiques qui existent, on peut citer :

### Preuve d'un logarithme discret d'une valeur donnée

Le protocole de Schnorr, pour prouver la connaissance d'un logarithme discret $x$ d'un élément de groupe public $h=g^{x}$.
Supposons que Peggy souhaite prouver à Victor qu'elle connaît un secret x tel que $g^{x}\mod p$, où $p$ est un grand nombre premier et $g$ un générateur du groupe multiplicatif modulo $p$. Peggy veut prouver qu’elle connaît $x$ sans le révéler.
Le protocole interactif se déroule comme suit :

#### Initialisation

Peggy et Victor s'accordent sur un grand nombre premier $p$ et un générateur $g$ du groupe multiplicatif $\mathbb {Z} _{p}^{*}$.
Peggy choisit un secret $x$, calcule $y=g^{x}\mod p$, puis transmet la valeur $y$ à Victor.

#### Répétition des étapes du protocole (un grand nombre de fois

Engagement : Peggy choisit un nombre aléatoire $r({\mbox{où }}r\in [0,p-2])$et calcule $C=g^{r}\mod p$. Elle envoie $C$ à Victor.
Défi : Victor choisit aléatoirement l'un des deux défis suivants :
* Soit il demande à Peggy de révéler $r$,
* Soit il demande à Peggy de révéler $(x+r)\mod (p-1)$.
Réponse : Selon le défi, Peggy répond comme suit :
* Si Victor demande $r$, Peggy lui transmet $r$, et Victor vérifie que $C=g^{r}\mod p$.
* Si Victor demande $(x+r)\mod (p-1)$, Peggy lui transmet cette valeur, et Victor vérifie que $C\cdot y=g(x+r)\mod p$

#### Sécurité du protocole

* Si Peggy connaît effectivement $x$, elle pourra toujours répondre correctement à l’un des deux défis.
* Si Peggy tente de tricher (sans connaître $x$), elle ne peut anticiper quel défi Victor choisira, et sa probabilité de réussir est de $0.5$ à chaque itération. En répétant le protocole plusieurs fois, cette probabilité devient arbitrairement faible.
Zéro-connaissance : Le protocole ne divulgue aucune information sur , car le protocole ne divulgue aucune information sur $x$, car
* La valeur r est aléatoire et indépendante de x.
* La valeur $(x+r)\mod (p-1)$peut être vue comme une version chiffrée de $x$ à l’aide d’un masque aléatoire $r$ (analogue au chiffrement par masque jetable ou one-time pad).
Grâce à ce protocole interactif, Peggy prouve qu’elle connaît le logarithme discret sans le révéler, ce qui peut servir dans des systèmes d’authentification sécurisée ou de signature numérique.

### Preuve de connaissance d’une information parmi plusieurs

Le protocole de Guillou-Quisquater, qui permet de prouver la connaissance d'un message clair derrière un chiffré RSA. Les preuves de connaissances dans RSA permettent de prouver la possession d'un secret lié à une clé publique $n=p\cdot q$. L'objectif est de permettre à un prouveur de démontrer qu’il connaît une valeur $x$ telle que $y=x^{e}\mod n$, sans révéler $x$. On fait finalement une preuve de connaissance de racine $e-{\mbox{ième}}$ qui est $x$. On répète le protocole t fois et les étapes sont les suivantes :
* Engagement : Le prouveur calcule un $r\in \mathbb {Z} _{n}$ aléatoire et envoie $t=r^{e}\mod n$.
* Défi : Le vérificateur envoie un défi $c$ inférieure à $2^{t}$.
* Réponse : Le prouveur envoie $s=r\cdot x^{c}\mod n$.
* Vérification : Le vérificateur calcule $s^{e}\mod n$ et vérifie si cela correspond à $t\cdot y^{c}\mod n$.

## Propriétés

Trois propriétés doivent être satisfaites :
* Complétude (completeness) : si le fournisseur de preuve et le vérificateur suivent le protocole alors le vérificateur doit toujours accepter la preuve.
Si le prouveur est honnête et utilise un témoin w valide pour lequel (x,w)∈R, alors le vérificateur accepte la preuve avec une probabilité de 1 :
Pr [V2 (x, engagement, défi, reponse) = 1 ] = 1. où V2 est un algorithme de vérification
* Robustesse (soundness) : si la proposition est fausse, aucun fournisseur de preuve malveillant ne peut convaincre un vérificateur « honnête » que la proposition est vraie et ceci avec une forte probabilité.
Le protocole est donc dit robuste s'il est possible, avec n transcriptions valides (x,engagement,challenge_i,reponse_i), où challenge_i=challjenge_j, d'extraire efficacement un témoin w tel que (x,w)∈R
* Zéro-connaissance (zero knowledge) : le vérificateur n'apprend de la part du fournisseur de preuve rien de plus que la véracité de la proposition, il n'obtient aucune information qu'il ne connaissait déjà sans l'apport du fournisseur de preuve.
Pour un vérificateur honnête, il existe un simulateur S qui, connaissant uniquement x et un défi/challenge, est capable de produire un transcript valide indiscernable d'une exécution honnête du protocole.
Formellement, pour chaque paire (x,w) ∈ R et chaque chall ∈ C :
S(x, chall) ≈ (x, com, chall, resp).
Si le vérificateur ne respecte pas la procédure, cette définition reste valable tant que le fournisseur de preuve (le prouveur) suit correctement le protocole.
Les deux premières propriétés sont les mêmes qui servent à définir un système de preuve interactive, qui est un concept plus général. C'est la troisième propriété qui fait "nulle de connaissance".

### Sécurité

La sécurité des preuves peut être classée en plusieurs catégories, suivant la sécurité attendue par les différentes notions de sécurité précédemment définies, c'est-à-dire la robustesse et le non-apport de connaissance. On parle alors de :
* preuve « calculatoire » : impossibilité pour un observateur de distinguer en un temps polynomial une preuve authentique d'une preuve forgée ou aléatoire
* preuve « statistique », ou parfaite : la distribution des preuves authentiques est la même que celle des preuves aléatoires ou forgées. Cela peut se voir de la même manière que pour les preuves calculatoires, en donnant une puissance de calcul infinie (ou non bornée) au distingueur.
La première ne rejette pas l'existence d'une méthode (mais celle-ci, si elle existe, n'aura pas une complexité polynomiale) alors que la preuve parfaite assure qu'aucune méthode n'existe (d'après la théorie de l'information).
De manière similaire, si la robustesse est statistique, le terme « preuve » sera utilisé, autrement si elle est calculatoire, le terme « argument » sera utilisé pour désigner la preuve.

### Construction générale

Une méthode pour construire des preuves sans divulgation de connaissances utilise ce qu'on appelle des protocoles Σ (ainsi nommés en raison de la communication en trois échanges qui fait penser à la lettre grecque Sigma). Un protocole Σ est un protocole interactif entre un prouveur et un vérifieur mettant en jeu trois échanges :
* L’engagement, qui est un premier message envoyé par le prouveur au vérifieur ;
* Le défi, qui est une réponse envoyée par le vérifieur ;
* La réponse, qui est le dernier message envoyé par le prouveur.
La sécurité d'un protocole Σ est très proche de celle d'une preuve sans divulgation de connaissance : la complétude, la robustesse spéciale et l'apport nul d'information avec un vérifieur honnête. La construction générale consiste alors à imposer l'honnêteté au vérifieur en l'obligeant à générer son défi indépendamment de l’engagement par le biais d’un schéma de mise en gage cryptographique.
De multiples preuves sans divulgation de connaissances reposent sur cette construction, par exemple le protocole de Schnorr, ou le schéma d'identification de Guillou-Quisquater. Une des raisons pouvant être qu'il est plus aisé de travailler sur les protocoles Σ, qui possèdent en plus des bonnes propriétés de régularité : il existe des constructions pour effectuer la conjonction et la disjonction de protocoles Σ. Propriétés que l'on n'a pas sur les preuves sans divulgation de connaissances génériques.

## Histoire

Le concept de preuve à divulgation nulle de connaissance (Zero Knowledge Proof ou ZKP) a été introduit en 1985 par Shafi Goldwasser, Silvio Micali et Charles Rackoff dans leur article fondateur intitulé "The Knowledge Complexity of Interactive Proof Systems". Ils ont montré qu'il était possible pour un prouveur de convaincre un vérificateur de la validité d'une déclaration sans divulguer aucune information supplémentaire. Cette avancée a posé les bases théoriques des preuves interactives et de la complexité des connaissances. Les travaux de Goldwasser et Micali leur ont valu le Prix Turing en 2012 pour leurs contributions majeures à la cryptographie : “une entité prouve à une autre entité qu’une proposition est vraie mais ne donne aucun autre élément que la véracité de la proposition” rien que ça!
En 1989, Jean-Jacques Quisquater et Louis Guillou proposent une explication pédagogique des ZKP dans leur article "How to Explain Zero-Knowledge Protocols to Your Children". Leur célèbre exemple, basé sur le conte Ali Baba et les Quarante Voleurs, a permis de vulgariser la notion auprès d’un public plus large en illustrant comment prouver la connaissance d’un secret sans le révéler.
Les travaux ultérieurs de Oded Goldreich, Silvio Micali et Avi Wigderson ont démontré que les ZKP ne se limitent pas à des problèmes spécifiques. En particulier, ils ont prouvé que tout problème de la classe NP possède un système de preuve à divulgation nulle de connaissance, ouvrant ainsi la voie à des applications universelles en cryptographie et en théorie de la complexité.
La transformée de Fiat-Shamir, introduite dans les années 1990, permet de convertir une preuve interactive en une preuve non interactive (NIZK) , rendant les ZKP plus pratiques pour des systèmes cryptographiques modernes, comme les signatures numériques.
Depuis les années 2000, les ZKP ont connu des avancées majeures grâce à l'amélioration des performances et des variantes plus efficaces.
Développés dans les années 2010, les zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) permettent de générer des preuves courtes et rapides à vérifier, avec des applications dans les blockchains et les cryptomonnaies.
Introduits plus récemment, les zk-STARKs (Zero-Knowledge Scalable Transparent Arguments of Knowledge) offrent des avantages en termes de transparence et de scalabilité en éliminant les configurations de confiance nécessaires aux zk-SNARKs.

### Applications des preuves à divulgation nulle de connaissance

L'une des principales motivations des ZKP est d'assurer que les clés publiques dans une infrastructure cryptographique, comme la norme X.509 (rfc 4210) de gestion des certificats, sont correctement formées. Ces preuves permettent de vérifier qu'un utilisateur qui enregistre une clé publique est bien en possession de la clé privée correspondante, le terme spécifique employé dans la rfc 4210 est de preuve de possession (POP) d’une clé privée évitant ainsi des comportements malveillants, comme la revendication d'une clé publique appartenant à un tiers.(preuves du logarithme discret d’une valeur donnée, preuve d’une isogénie).
Dans le contexte des technologies distribuées (DLT) et des blockchains, les ZKP offrent une solution cryptographique pour préserver la confidentialité des transactions. Alors que les blockchains publiques rendent les transactions visibles par tous, les ZKP permettent de prouver qu'une transaction est valide sans révéler d'informations sensibles. Contrairement aux environnements d'exécution sécurisés (TEE), comme Intel SGX, qui peuvent être vulnérables à des attaques par canaux auxiliaires, les ZKP fournissent une approche robuste et "privacy by design" pour protéger les données privées tout en permettant leur validation.
Depuis son introduction, cette notion a évolué pour devenir un pilier des technologies modernes de confidentialité, avec des applications allant de la vérification des identités numériques aux transactions privées sur les blockchains.
Les preuves à divulgation nulle de connaissance jouent un rôle central dans la sécurisation des protocoles cryptographiques. Elles permettent de transformer un protocole passivement sécurisé en un protocole activement sécurisé. Pour cela, chaque partie doit accompagner les messages qu'elle envoie d'une preuve à divulgation nulle de connaissance démontrant que le message a été généré correctement, conformément aux spécifications du protocole. Cette exigence empêche les adversaires malveillants de modifier les messages ou d'agir de manière non conforme.

#### Systèmes d’authentification sécurisés

Les ZKP permettent à une partie de prouver son identité à une autre sans révéler d'informations sensibles, comme un mot de passe. Cette méthode est particulièrement utile lorsque les mots de passe sont courts ou peu aléatoires, nécessitant des protocoles adaptés tels que les « Zero-Knowledge Password Proofs » [1].
En août 2021, Cloudflare a adopté le protocole « one-out-of-many proofs » pour des vérifications privées sur le web utilisant des matériels tiers, améliorant ainsi la sécurité tout en garantissant la confidentialité [2].

#### Comportement éthique dans les protocoles cryptographiques

Les ZKP sont intégrées dans les protocoles cryptographiques pour assurer un comportement honnête tout en préservant la confidentialité. Elles permettent à un utilisateur de prouver que ses actions respectent les règles d’un protocole sans divulguer ses secrets, grâce aux propriétés de solidité et de divulgation nulle [3][4].

#### Désarmement nucléaire

En 2016, le Princeton Plasma Physics Laboratory et l’Université de Princeton ont démontré une application des ZKP pour les négociations de désarmement nucléaire. Cette technique permet de vérifier si un objet est une arme nucléaire sans révéler d’informations sensibles sur sa structure interne, ce qui pourrait transformer les inspections internationales en matière de désarmement [5].

#### Blockchain et cryptomonnaies

Les ZKP jouent un rôle essentiel dans la blockchain, notamment pour améliorer la confidentialité et l’anonymat des transactions. Elles ont été intégrées dans des protocoles comme Zerocoin et Zerocash, donnant naissance aux cryptomonnaies Zcoin (rebaptisée Firo) et Zcash en 2016.
* Zerocoin : Utilise un modèle de mélange intégré garantissant l’anonymat sans nécessiter la confiance d’intermédiaires .
* Zerocash : Ajoute une couche de confidentialité en masquant le montant des transactions. Cependant, ce niveau de confidentialité peut engendrer des risques, comme une hyperinflation indétectable en cas de fraude [6].
En 2018, les Bulletproofs ont été introduits pour permettre des preuves non interactives sans nécessiter d’installation de confiance. Cette technologie a été intégrée dans le protocole Mimblewimble (utilisé par les cryptomonnaies Grin et Beam) et Monero [7].
En 2019, Firo a adopté le protocole Sigma, une amélioration du protocole Zerocoin, suivie du protocole Lelantus, qui masque l’origine et le montant des transactions [8].

#### Identifiants décentralisés (DID)

Les ZKP renforcent la confidentialité dans les systèmes d’identités décentralisées en permettant aux utilisateurs de prouver des attributs spécifiques (par exemple, l’âge) sans révéler leurs données personnelles. En intégrant les ZKP, ces systèmes offrent une couche supplémentaire de sécurité et réduisent les risques de violations de données et de vols d’identité [9].