Preuves à Divulgation Nulle de Connaissance

Une preuve à divulgation nulle de connaissance permet à un prouveur de convaincre un vérificateur de la véracité d'une affirmation sans révéler autre chose que cette véracité, une capacité contre-intuitive aux applications cryptographiques étendues.

Definition

Une preuve à divulgation nulle de connaissance est un protocole interactif (ou non interactif) dans lequel un prouveur convainc un vérificateur de la véracité d'une affirmation, de telle sorte que le vérificateur n'apprend rien d'autre que la validité de l'affirmation, formalisé par un simulateur qui reproduit la vue du vérificateur sans le témoin.

Scope

Ce sujet couvre les systèmes de preuve interactifs et leurs variantes à divulgation nulle de connaissance : les propriétés définissantes de complétude, de correction (ou robustesse) et de divulgation nulle de connaissance ; le paradigme de simulation ; les preuves de connaissance ; la transformation de Fiat-Shamir pour les preuves non interactives ; et les systèmes succincts modernes (zk-SNARKs et zk-STARKs). Il aborde les applications à l'authentification et à la vérification préservant la confidentialité. Il exclut la théorie de la complexité plus large des preuves interactives et les protocoles (MPC) qui utilisent la divulgation nulle de connaissance comme sous-composant.

Core questions

• Comment une preuve peut-elle transmettre la conviction de la vérité sans divulguer d'autres informations ?
• Que garantissent respectivement la complétude, la correction et la propriété de divulgation nulle de connaissance ?
• Comment l'existence d'un simulateur capture-t-elle l'idée de « ne rien apprendre » ?
• Comment les preuves interactives sont-elles rendues non interactives via la transformation de Fiat-Shamir ?
• Comment les preuves succinctes (SNARKs, STARKs) rendent-elles la divulgation nulle de connaissance pratique à grande échelle ?

Key concepts

• système de preuve interactif
• complétude et correction
• propriété de divulgation nulle de connaissance
• simulateur
• preuve de connaissance
• transformation de Fiat-Shamir
• divulgation nulle de connaissance non interactive (NIZK)
• zk-SNARKs et zk-STARKs
• schémas d'engagement

Key theories

Le paradigme de simulation

Un protocole est à divulgation nulle de connaissance si, pour chaque vérificateur, il existe un simulateur efficace qui, sans accès au témoin secret, produit une transcription indiscernable d'une interaction réelle — formalisant l'idée que le vérificateur n'apprend rien.

Complétude, correction et preuves de connaissance

Une preuve interactive est complète si des prouveurs honnêtes convainquent des vérificateurs honnêtes et correcte si les fausses affirmations sont rejetées avec une forte probabilité ; une preuve de connaissance garantit en outre, via un extracteur de connaissance, que le prouveur possède réellement le témoin.

Mechanisms

Un protocole canonique à trois mouvements (sigma) implique que le prouveur envoie un engagement, le vérificateur envoie un défi aléatoire, et le prouveur répond ; la correction découle de l'incapacité du prouveur à répondre à tous les défis sans le témoin, et la divulgation nulle de connaissance provient de la capacité du simulateur à falsifier des transcriptions en choisissant le défi en premier. La transformation de Fiat-Shamir remplace le défi du vérificateur par un hachage de l'engagement, produisant une preuve non interactive. Les systèmes succincts utilisent des engagements polynomiaux et des circuits arithmétiques pour produire des preuves courtes et rapides à vérifier.

Clinical relevance

Les preuves à divulgation nulle de connaissance permettent la confidentialité et la scalabilité dans les systèmes déployés : les cryptomonnaies préservant la confidentialité (Zcash) masquent les détails des transactions tout en prouvant leur validité, les rollups de blockchain utilisent des preuves succinctes pour compresser les calculs, les identifiants anonymes et les systèmes d'identité numérique prouvent des attributs (âge, citoyenneté) sans les révéler, et les schémas d'authentification prouvent la possession d'un secret sans le divulguer.

Evidence & guidelines

Les constructions à divulgation nulle de connaissance constituent un domaine de normalisation actif (l'effort de normalisation de la communauté ZKProof). Les systèmes de production s'appuient sur des bibliothèques SNARK et STARK bien examinées ; cependant, les SNARKs nécessitant une configuration de confiance exigent une conception minutieuse de la cérémonie, tandis que les STARKs évitent la configuration de confiance au prix de preuves plus volumineuses. La correction dépend d'hypothèses cryptographiques et, pour Fiat-Shamir, du modèle de l'oracle aléatoire.

History

Goldwasser, Micali et Rackoff ont introduit les preuves interactives et la divulgation nulle de connaissance en 1985, la version journalisée paraissant en 1989. Goldreich, Micali et Wigderson ont montré que chaque énoncé NP possède une preuve à divulgation nulle de connaissance (1987). La transformation de Fiat-Shamir (1986) a rendu les preuves non interactives. Les années 2010 ont vu l'émergence des arguments non interactifs succincts (zk-SNARKs) et des STARKs transparents, faisant passer la divulgation nulle de connaissance de la théorie aux produits de blockchain et de confidentialité.

Key figures

• Shafi Goldwasser
• Silvio Micali
• Charles Rackoff
• Oded Goldreich
• Amos Fiat
• Adi Shamir

Seminal works

• goldwasser1989
• katz2020
• goldreich2001

Frequently asked questions

Quelle est une intuition simple pour la divulgation nulle de connaissance ?

Imaginez prouver que vous pouvez distinguer deux objets visuellement identiques en identifiant à plusieurs reprises lequel une partie cachée a échangé : chaque bonne réponse augmente la confiance que vous pouvez les distinguer, mais le vérificateur n'apprend jamais comment. Répéter un défi-réponse de nombreuses fois rend la tricherie astronomiquement improbable tout en ne révélant aucun secret.

Les preuves à divulgation nulle de connaissance nécessitent-elles une interaction ?

La définition originale est interactive, mais la transformation de Fiat-Shamir et les constructions non interactives dédiées (NIZK, SNARKs, STARKs) produisent une chaîne de preuve unique que n'importe qui peut vérifier sans interagir, ce qui les rend utilisables sur les blockchains.