Intuition des ZKP : la grotte d’Ali Baba

Une preuve à divulgation nulle de connaissance (ZKP) permet à un prouveur de convaincre un vérificateur qu’il connaît un secret (ou qu’une assertion est vraie) sans révéler le secret lui-même. Trois propriétés : complétude, solidité et divulgation nulle de connaissance.

Si le prouveur connaît le secret, il peut toujours convaincre le vérificateur. Un prouveur honnête qui suit le protocole réussira avec une probabilité égale à 1 (ou écrasante). Le vérificateur ne rejettera pas une preuve valide.

Un prouveur malhonnête (qui ne connaît pas le secret) ne peut convaincre le vérificateur qu’avec une probabilité négligeable. Chaque tour d’interaction réduit la probabilité de tricherie ; après k tours, la probabilité de réussite d’un tricheur est d’au plus 2^{-k}.

Le vérificateur n’apprend rien au-delà du fait que l’assertion est vraie. Formellement : il existe un simulateur qui, sans connaître le secret, produit une transcription indiscernable de celle d’une interaction réelle entre un prouveur et un vérificateur. Le vérificateur n’acquiert aucune connaissance supplémentaire.

Une grotte possède un passage circulaire avec une porte magique au milieu. La prouveuse (Alice) affirme qu’elle connaît le mot de passe. Le vérificateur (Bob) attend à l’extérieur. Alice entre et part à gauche ou à droite. Bob lui crie par quel côté sortir. Si Alice connaît le mot de passe, elle sort toujours du bon côté. Probabilité de tricherie par tour : 1/2.

Après 20 tours, un tricheur réussit avec une probabilité de 2^{-20}, soit environ 1 sur un million. Alice, qui connaît le mot de passe, réussit à chaque fois. Bob n’apprend jamais le mot de passe : il voit seulement Alice sortir du côté demandé. Il s’agit d’une divulgation nulle de connaissance.

Les ZKP interactives nécessitent des échanges dans les deux sens entre le prouveur et le vérificateur. Les ZKP non interactives (NIZKs) utilisent la transformation de Fiat-Shamir : elles remplacent le défi aléatoire du vérificateur par un hachage de l’engagement (le hachage joue le rôle d’un oracle aléatoire). Cela produit une chaîne de preuve unique que n’importe qui peut vérifier.

Une ZKP est une preuve de connaissance (PoK) si la stratégie du prouveur implique qu’il pourrait extraire le secret. C’est plus fort que de prouver simplement qu’une assertion est vraie. Les signatures ECDSA et Schnorr sont des preuves de connaissance non interactives de la clé privée.

Authentification par mot de passe sans envoyer le mot de passe. Vérification de l’âge sans révéler la date de naissance. Preuves d’appartenance à un intervalle (votre salaire se situe dans un intervalle) sans révéler le salaire. Blockchain : prouver que vous connaissez une transaction valide sans révéler la transaction.

Zéro connaissance parfaite : la sortie du simulateur est identique à la transcription réelle. ZK statistique : indiscernable, sauf avec une probabilité négligeable. ZK computationnelle : indiscernable pour des vérificateurs fonctionnant en temps polynomial. Des garanties moins fortes permettent des preuves plus efficaces.

La grotte est un protocole en trois étapes : engagement → défi → réponse. On l'appelle formellement un protocole Sigma. La plupart des ZKP pratiques (Schnorr, Pedersen, Fiat-Shamir) sont des protocoles Sigma ou des compositions de tels protocoles. Le nom vient de la forme Σ du diagramme de flux des messages.

Après combien de tours du protocole de la grotte d'Ali Baba la probabilité de réussite d'un tricheur devient-elle inférieure à 1/1000 ?

Les ZKP prouvent la connaissance d'un secret sans le révéler. Trois propriétés : complétude, solidité et zéro connaissance. La grotte d'Ali Baba illustre une ZKP interactive. Ensuite : protocoles Sigma et identification de Schnorr.