Une preuve cryptographique peut cacher son secret en rendant le simulateur manquant difficile à prouver

Le truc n’est pas de prouver que le secret est caché

Commençons par la version la plus simple du zéro connaissance.

Alice veut convaincre Bob qu’une grille de Sudoku a une solution. Si elle envoie la solution, Bob est convaincu, mais le puzzle est gâché. Ce qu’elle veut est plus étrange : une preuve qu’une solution existe, sans révéler la solution.

C’est la promesse d’une preuve à divulgation nulle de connaissance. Le prouveur (Alice) convainc le vérificateur (Bob) qu’un énoncé est vrai tout en ne révélant rien au-delà de la vérité de l’énoncé.

Le problème est que cette promesse coûte quelque chose. Une preuve mathématique ordinaire a deux traits confortables. Elle est un seul message : on l’écrit, on la remet, et l’on s’en va. Et elle est parfaitement saine : un énoncé faux n’a aucune preuve valide. Les résultats classiques d’impossibilité disent que le zéro connaissance doit abandonner ces deux traits — et pas seulement les deux ensemble ; chacun est interdit à lui seul.

D’abord, une preuve à divulgation nulle de connaissance a besoin d’une conversation. Si Alice envoie un seul message, sans dispositif de confiance arrangé à l’avance, la garantie de zéro connaissance s’effondre — et cela reste vrai quelle que soit la quantité de solidité que l’on accepte d’échanger.

Ensuite, une preuve à divulgation nulle de connaissance a besoin d’une petite tolérance à l’erreur. Exiger une solidité parfaite détruit discrètement l’interaction aussi : un vérificateur qui ne peut jamais être trompé, quels que soient ses choix aléatoires, pourrait tout aussi bien fixer ces choix à l’avance — et dès que le vérificateur devient prévisible, Alice peut répondre à tout dans un seul message, ce qui est exactement le cas qui avait déjà cassé la propriété.

L’article de Rahul Ilango porte sur une façon de contourner ce double mur. Pas en prétendant que le mur n’existe pas, et pas en produisant du zéro connaissance classique dans le cadre impossible. Le mouvement est plus subtil : affaiblir ce que « ne révèle rien » signifie, mais l’affaiblir d’une manière qui préserve les propriétés de sécurité que les cryptographes peuvent réellement tester.

Le résultat s’appelle zéro connaissance effectif.

L’ancien test : un simulateur existe

La manière classique de formaliser le zéro connaissance utilise un auxiliaire fictif appelé simulateur.

L’idée est la suivante : imaginez Jane, qui ne connaît pas le secret d’Alice. Si Jane peut générer, entièrement seule, des preuves qui ressemblent exactement aux preuves que Bob aurait reçues d’Alice, alors les preuves d’Alice n’ont rien appris de nouveau à Bob. Jane pouvait déjà imiter l’expérience sans le secret d’Alice.

Le zéro connaissance classique demande donc un vrai simulateur. Il doit exister un algorithme efficace capable de produire des preuves d’apparence authentique sans connaître le secret — le témoin, dans le jargon ; pour un Sudoku, le témoin est simplement la grille résolue.

Cette définition est puissante, mais c’est aussi précisément là que mord l’ancienne impossibilité. Voici l’intuition. Une preuve vraiment non interactive n’est qu’une chaîne de caractères. Une fois que Bob a cette chaîne, il peut la montrer à quelqu’un d’autre : il a gagné la capacité de prouver l’énoncé à d’autres, ce qui ressemble déjà à plus que « rien ». Les théorèmes classiques affûtent cette intuition pour donner les impossibilités ci-dessus.

Une version méga-Sudoku de la différence

Voici une façon volontairement simplifiée de sentir la différence.

N’utilisez pas un Sudoku ordinaire 9 par 9 pour la partie sérieuse de l’analogie. Il est trop petit et trop fini : un ordinateur peut simplement le résoudre, ou prouver qu’il n’a pas de solution. Imaginez plutôt une famille de puzzles MegaSudoku(n). On met la règle habituelle à l’échelle : choisir une taille de bloc n, poser N = n^2, et construire une grille N par N divisée en blocs n par n, avec N symboles. Le Sudoku ordinaire n’est que le minuscule cas n = 3, N = 9 : une grille 9 par 9, des blocs 3 par 3 et neuf symboles. L’histoire de complexité de preuve ne commence que lorsque n peut grandir, et lorsque la grille peut porter des gadgets supplémentaires qui la font se comporter comme une formule SAT déguisée en Sudoku. Une formule SAT n’est qu’une liste de contraintes oui/non : peut-on affecter des valeurs vrai/faux aux variables de sorte que chaque contrainte soit satisfaite ?

Le témoin reste facile à imaginer. Alice connaît un remplissage complet et valide du méga-Sudoku. Bob veut être convaincu qu’un tel remplissage existe, mais Alice ne veut pas le révéler. Si elle envoie tout le remplissage, Bob est convaincu, mais le secret a disparu.

Dans la version classique du zéro connaissance, Alice et Bob interagissent. Un ancien modèle mental utilise des tuiles couvertes. Alice cache la grille résolue, renomme secrètement les symboles avant chaque tour, et laisse Bob inspecter une contrainte locale choisie au hasard : une ligne, une colonne, une boîte ou un gadget. Si les cases ouvertes montrent des symboles tous différents, Bob gagne en confiance. Puis tout est recouvert et les symboles sont fraîchement renommés. (Une difficulté : les indices donnés du puzzle ont besoin d’une astuce supplémentaire, parce que renommer les symboles les cache aussi. La note ci-dessous explique comment les protocoles classiques résolvent cela ; l’image-jouet suffit pour la suite.)

Ce n’est pas le protocole de l’article. C’est le modèle mental du zéro connaissance classique :

• Alice et Bob échangent.
• Bob choisit des vérifications aléatoires.
• Alice ne révèle qu’une cohérence locale, pas toute la solution.
• La preuve de confidentialité fonctionne en montrant que la vue de Bob aurait pu être générée sans la solution secrète d’Alice.

Le zéro connaissance classique repose donc sur un fait positif :

Un simulateur existe vraiment.

Retirez maintenant les parties confortables. Alice envoie une seule chaîne de preuve et s’en va. Il n’y a pas de setup de confiance, pas de chaîne aléatoire partagée préparée à l’avance, et Bob ne doit jamais accepter un puzzle faux. C’est le cadre dans lequel le zéro connaissance classique ne peut pas survivre.

Un personnage de plus est nécessaire avant l’astuce. Fixez un système formel : un système de preuve formel, au sens des logiciens — un ensemble fixé d’axiomes plus des règles mécaniques pour vérifier des preuves mathématiques écrites. ZFC, les axiomes standard des mathématiques, en est l’exemple canonique. Tout ce qui suit est formulé relativement à un système choisi à l’avance, et le choix est flexible : la construction fonctionne pour tout système que vous fixez, ZFC inclus.

(Une note de vocabulaire, empruntée à l’article lui-même : ici, « système de preuve » signifie toujours ce système formel — le système qui vérifie les preuves mathématiques — jamais les messages qu’Alice envoie. La mécanique d’Alice et de Bob s’appelle « le prouveur et le vérificateur ».)

La version à la Gödel garde l’histoire du méga-Sudoku mais change la preuve.

Choisissez un second système de contraintes de même taille affichée, appelons-le D. Pour l’histoire, S et D sont deux MegaSudoku(n) dans le même format. En coulisse, D peut avoir commencé comme une formule logique difficile d’une autre taille ; si nécessaire, on peut le compléter avec des contraintes factices inoffensives pour qu’il tienne dans la même grille. D est construit à partir d’une formule logique qui est réellement insatisfiable : aucune affectation de valeurs ne peut rendre toutes ses contraintes vraies, comme un puzzle cassé n’a pas de grille complète légale. Un exemple-jouet serait une formule qui exige à la fois « X est vrai » et « X est faux ». D n’a donc pas de remplissage valide.

Mais D ne doit pas être un puzzle cassé facile à exposer. L’exemple-jouet ci-dessus échoue : n’importe quel système formel réfute « X et non-X » en une ligne. D doit être faux d’une manière que le système choisi ne peut pas certifier par un argument court. Si le système pouvait réfuter D par une courte preuve, l’histoire ci-dessous s’effondrerait : la route alternative qui aurait pu produire des preuves sans le secret d’Alice pourrait être formellement exclue, et avec elle la garantie de confidentialité. D est donc choisi dans une famille que le système fixé ne peut pas réfuter efficacement : il n’existe pas de courte preuve, dans ce système, que D n’a pas de solution.

La preuve en un seul message d’Alice porte alors sur un énoncé soit/ou :

soit le vrai méga-Sudoku S a une solution, soit le leurre D a une solution.

C’est le lien logique. D n’est pas généré par un procédé magique qui rend S vrai. La preuve ne dit pas « D n’a pas de solution, donc S a une solution ». Elle prouve la disjonction S ou D. La solidité parfaite dit qu’une disjonction fausse ne peut pas avoir de preuve valide. Puisque D est faux en réalité — il n’a pas de solution — la seule façon que la disjonction soit vraie est que S soit vrai. Donc si la preuve est acceptée, S doit avoir une solution. Le leurre ne peut pas rendre vrai un S faux.

Mais pour la partie de type zéro connaissance, demandez ce qui arriverait si D avait une solution. Cette solution-leurre servirait de témoin alternatif. Elle permettrait à quelqu’un de produire des preuves sans connaître la vraie solution du méga-Sudoku d’Alice — un simulateur, autrement dit. En réalité D n’a pas de solution, donc cette route de simulation est fermée. Le point est que le système formel ne peut pas prouver efficacement qu’elle est fermée.

D a donc deux tâches. Pour la solidité, D est faux, donc une preuve valide de « S ou D » force S. Pour le zéro connaissance effectif, D est difficile à réfuter, donc le système formel ne peut pas exclure rapidement la route-leurre qui aurait rendu la simulation possible.

Le test de sécurité n’est donc plus :

Pouvons-nous prouver qu’un simulateur existe vraiment ?

Il devient :

Votre système formel peut-il prouver efficacement que le simulateur est impossible ?

Si la réponse est non, quelque chose d’étonnamment fort suit : toute garantie de sécurité qui (a) peut être observée en exécutant un test, et (b) découle prouvablement — dans ce système formel — de l’existence d’un simulateur, tient effectivement. Une attaque réussie contre l’une d’elles constituerait elle-même la courte réfutation manquante, et cette courte réfutation n’existe pas. C’est la partie « effective » du zéro connaissance effectif.

Le contraste de salle de classe est donc :

Zéro connaissance classique : les preuves sont sûres parce qu’un simulateur existe.

Zéro connaissance effectif à la Gödel : les preuves sont traitées comme sûres pour les tests de sécurité observables parce que le système formel ne peut pas prouver efficacement que le simulateur est impossible.

La seconde affirmation est plus faible. C’est aussi pourquoi l’article peut garder les trois traits qui avaient brisé la version classique : un message, aucun setup et une solidité parfaite.

Le nouveau test : vous ne pouvez pas prouver que le simulateur est absent

La relaxation d’Ilango change la question.

Le zéro connaissance classique demande :

Un simulateur existe-t-il ?

Le zéro connaissance effectif demande quelque chose de plus faible :

Votre système formel choisi peut-il prouver efficacement qu’aucun simulateur n’existe ?

Cela ressemble à une esquive technique, mais c’est l’idée centrale. La construction vit dans un état étrange : aucun simulateur n’existe réellement — l’article est explicite là-dessus — mais le système formel que vous avez fixé ne peut pas prouver efficacement qu’il n’existe pas. Si chaque mauvaise conséquence qui vous importe exigerait une telle réfutation, le système se comporte encore comme du zéro connaissance pour ces conséquences.

C’est ici que Gödel entre en scène. Pas comme décoration, et pas comme « Gödel rend la crypto sûre ». Le lien relève de la théorie des preuves. Un système formel est dit optimal s’il est, en un sens précis, le meilleur possible : chaque fois qu’un système formel quelconque peut réfuter une formule du type pertinent avec une courte preuve, le système optimal le peut aussi, avec une preuve au plus polynomialement plus longue. Krajíček et Pudlák ont conjecturé en 1989 qu’aucun système de preuve optimal n’existe : quel que soit le système fixé, un autre système prouve certaines familles d’énoncés vrais bien plus succinctement. C’est l’une des conjectures centrales de la complexité des preuves, et c’est le cousin fini, en complexité, du théorème d’incomplétude de Gödel : certains énoncés vrais n’ont pas de courte preuve dans le système que vous avez fixé — non parce qu’ils seraient improuvables en principe, mais parce que tout système fixé laisse certaines vérités courtes sans courte preuve.

L’article suppose cette conjecture (dans une forme « infiniment souvent » un peu plus forte, standard quand des conjectures sont utilisées cryptographiquement). Le gain, par un théorème de Krajíček et Pudlák, est concret : pour tout système formel, il existe une suite de formules réellement insatisfiables que ce système ne peut pas réfuter par de courtes preuves — et, point crucial, qu’un algorithme efficace peut générer. Cette dernière propriété, l’uniformité, transforme toute l’idée d’une affirmation d’existence en un véritable algorithme qu’Alice peut exécuter : ses leurres D sortent d’une chaîne de production, pas du néant.

Le mouvement cryptographique consiste à mettre ce manque de puissance de preuve au travail.

Ce que fait la construction

Voici la construction de l’article, ramenée à sa forme.

Fixez un système formel — ZFC, par exemple. Sous l’hypothèse de complexité des preuves, il existe une suite efficacement générable de formules réellement insatisfiables, mais pour lesquelles le système formel n’a pas de courte preuve d’insatisfiabilité.

Construisez maintenant une preuve en un message de cette forme :

soit le vrai énoncé est satisfiable, soit cette formule spéciale difficile est satisfiable.

La formule spéciale difficile n’est pas satisfiable. Donc, si la machinerie de preuve sous-jacente est parfaitement saine, accepter le message signifie encore que le vrai énoncé est vrai. C’est ce qui donne la solidité parfaite.

Mais pour la sécurité de type zéro connaissance, imaginez que la formule spéciale difficile soit satisfiable. Son témoin pourrait alors servir à simuler des preuves sans connaître le vrai témoin. La formule n’est pas satisfiable en réalité — mais le système formel ne peut pas le prouver efficacement. Il ne peut donc pas prouver efficacement que le simulateur est impossible.

C’est la charnière. Le système ne cache pas le secret en produisant un simulateur classique. Il cache le secret, pour une grande classe de tests de sécurité observables, derrière l’incapacité du système formel à certifier que le simulateur est absent.

Ce que l’article affirme

Le théorème principal arrive par couches. Le résultat central est celui-ci :

Sous une hypothèse cryptographique standard — l’existence de preuves non interactives à indistinguabilité de témoin, objets bien étudiés qui découlent de plusieurs paquets d’hypothèses établis — et sous la conjecture de complexité des preuves selon laquelle aucun système de preuve optimal (infiniment souvent) n’existe, l’article construit, pour tout choix de système formel, un prouveur et un vérificateur en un message pour NP/SAT avec solidité parfaite et sans setup, qui sont effectivement zéro connaissance relativement à ce système. (NP/SAT est le « plus grand commun dénominateur » standard des problèmes de type puzzle ; le méga-Sudoku est l’un de ses costumes.)

Pour l’affirmation plus large sur la préservation des propriétés de sécurité falsifiables, l’article ajoute une autre hypothèse standard, la croyance de dérandomisation P = BPP (en gros : le hasard ne donne pas de pouvoir essentiel supplémentaire aux algorithmes).

Traduit hors du langage des théorèmes :

• La preuve est un seul message.
• Il n’y a pas de setup de confiance.
• Les énoncés faux ne peuvent pas être prouvés.
• Le prouveur n’est pas zéro connaissance classique — il n’a pas de simulateur.
• Mais toute conséquence falsifiable, basée sur des jeux, du zéro connaissance classique peut être obtenue dans ce cadre.

« Falsifiable » compte. Cela signifie qu’un échec de sécurité peut être testé en faisant tourner un adversaire dans un jeu. Beaucoup de définitions de sécurité cryptographique ont cette forme : l’adversaire peut-il distinguer deux chiffrés, inverser une fonction, récupérer un témoin ou gagner une expérience spécifiée ? Le théorème donne un prouveur pour chaque propriété falsifiable, une à la fois. Un seul prouveur jouissant de toutes les propriétés falsifiables à la fois est probablement impossible — l’ancienne attaque de réutilisabilité (« Bob peut montrer la preuve à d’autres ») est elle-même une propriété falsifiable, et elle échoue réellement ici. La proposition de l’article est qu’un seul prouveur peut plausiblement couvrir toutes les propriétés falsifiables naturelles — celles qui apparaissent réellement dans la pratique cryptographique — mais cette partie est un théorème conditionnel reposant sur une notion informelle de « naturel », plus une conjecture explicite. La garantie vise les échecs observables, pas toute signification philosophique ou simulationnelle du secret.

Un corollaire concret mérite d’être nommé : la construction donne les premières preuves non interactives witness hiding avec un prouveur uniforme — « une preuve d’un puzzle ne vous aide pas à trouver sa solution », sans interaction et sans setup — un objet au son modeste qui résistait à la construction depuis des décennies.

Ce que cela ne dit pas

Cela ne dit pas que les anciens théorèmes d’impossibilité étaient faux. La construction les évite en changeant la définition.

Cela ne donne pas du zéro connaissance ordinaire, classique, sans interaction, sans setup et avec solidité parfaite. L’article dit explicitement que le prouveur construit n’a pas de simulateur.

Cela ne signifie pas que la preuve ne peut pas être réutilisée. Une preuve en un message peut toujours être montrée à quelqu’un d’autre ; l’article ne préserve pas les propriétés de type déniabilité. (Le zéro connaissance non interactif avec setup de confiance a la même limite.)

Cela ne signifie pas que c’est un protocole pratique prêt à être déployé. C’est de la théorie de la complexité et des fondements cryptographiques. Le résultat dépend d’hypothèses majeures de complexité des preuves et de cryptographie, et la construction porte sur ce qui est possible en principe.

Cela ne fait pas de « Gödel » une primitive de sécurité magique. Le lien avec Gödel passe par les systèmes de preuve, les systèmes de preuve optimaux et des analogues finis de l’incomplétude. L’intuition utilisable n’est pas « l’incomplétude protège votre mot de passe ». Elle est : si un système formel ne peut pas prouver efficacement qu’un simulateur est impossible, alors les attaques qui exigeraient cette preuve peuvent être bloquées au niveau des définitions de sécurité.

Pourquoi c’est intéressant quand même

La cryptographie transforme souvent la difficulté en sécurité. La factorisation est difficile, donc les hypothèses de type RSA deviennent utiles. Les problèmes de réseaux sont difficiles, donc la cryptographie sur réseaux devient utile. Ici, la difficulté est plus étrange : non pas « difficile de calculer un secret », mais « difficile de prouver qu’un certain objet de preuve ne peut pas exister ».

C’est pourquoi l’article paraît inhabituel. Il traite les axiomes et les systèmes formels presque comme des ressources cryptographiques. L’impossibilité habituelle dit qu’il existe une tension entre solidité et simulation. Le mouvement d’Ilango consiste à placer cette tension derrière un rideau de théorie des preuves : le simulateur est absent, mais le système formel ne peut pas exposer efficacement cette absence.

Pour un lecteur, la partie surprenante n’est pas que cela remplacera les systèmes zéro connaissance d’aujourd’hui. Ce ne sera probablement pas le cas, du moins pas directement. La partie surprenante est qu’une limitation de la logique mathématique peut être utilisée constructivement : pas seulement comme un mur, mais comme une forme de couverture.

Quelle est la solidité des preuves ?

C’est un article de théorème, donc « preuve » signifie autre chose que dans un article de biologie ou d’astronomie. La question n’est pas de savoir si une expérience s’est répliquée. La question est de savoir si les définitions, les hypothèses et la chaîne de preuve soutiennent l’affirmation.

La preuve est formelle, et l’article est explicite sur ses hypothèses. Ces hypothèses ne sont pas légères. Les preuves non interactives à indistinguabilité de témoin sont des objets standard en cryptographie et découlent de plusieurs paquets d’hypothèses établis. La conjecture de non-existence de système de preuve optimal est une conjecture centrale de la complexité des preuves. P = BPP est une croyance de dérandomisation standard utilisée seulement pour le théorème plus large sur les propriétés falsifiables.

L’article soutient aussi que les hypothèses sont le bon prix, pas un échafaudage arbitraire : il prouve une réciproque montrant qu’elles sont essentiellement nécessaires — si de telles constructions existent, alors les preuves non interactives à indistinguabilité de témoin doivent exister, et (en accordant les fonctions à sens unique standard) aucun système de preuve optimal ne peut exister. Et les hypothèses sont « gagnant-gagnant » : réfuter l’une d’elles serait déjà une découverte majeure en complexité des preuves, cryptographie ou théorie de la complexité.

Mais comme le résultat est conditionnel, la confiance l’est aussi. Si ces hypothèses échouent, l’interprétation du théorème change. Et même si elles tiennent, la garantie n’est pas le zéro connaissance classique complet ; c’est la version relaxée, formulée en théorie des preuves, de l’article.

La bonne confiance est donc élevée sur le fait que l’article établit un résultat de possibilité conditionnel cohérent ; modérée sur le fait que ses hypothèses décrivent le monde cryptographique où nous vivons ; et faible pour toute conséquence pratique immédiate.

Pourquoi c’est important

L’article ouvre une route que l’on pensait fermée.

La théorie classique dit : le zéro connaissance complet ne peut pas être un seul message sans setup, et ne peut pas être parfaitement solide. L’article d’Ilango dit : si l’on demande les conséquences du zéro connaissance qui peuvent être testées dans des jeux de sécurité, et si l’on permet à la définition de sécurité de dépendre de ce qu’un système formel peut ou ne peut pas réfuter efficacement, alors une grande partie du comportement utile peut être récupérée — avec un message, sans setup et avec solidité parfaite.

Ce n’est pas un petit ajustement définitionnel. C’est une autre façon de penser les garanties cryptographiques. Au lieu de demander seulement ce qui existe, demander ce que votre système formel peut exclure. Au lieu de traiter l’improuvabilité comme une nuisance philosophique, l’utiliser comme structure.

Le monde pratique ne changera peut-être pas demain. Mais la carte conceptuelle, elle, change. Il existe maintenant un sens formel dans lequel « personne ne peut prouver efficacement que le secret a fui » peut être assez fort pour récupérer beaucoup des protections fondées sur les jeux que l’on voulait obtenir de « le secret n’a pas fui ».

Voilà pourquoi Gödel appartient au titre.

Résumé propre

Les preuves à divulgation nulle de connaissance permettent à un prouveur de convaincre un vérificateur qu’un énoncé est vrai sans révéler le témoin. Les résultats classiques d’impossibilité disent que le zéro connaissance ne peut pas être comprimé dans un seul message sans setup, et ne peut pas avoir de solidité parfaite. L’article de Rahul Ilango ne réfute pas ces impossibilités. Il définit une notion plus faible, le zéro connaissance effectif : au lieu d’exiger qu’un simulateur existe vraiment, il exige qu’un système de preuve choisi — un système formel comme ZFC — ne puisse pas prouver efficacement qu’aucun simulateur n’existe. Sous de grandes hypothèses de cryptographie (preuves non interactives à indistinguabilité de témoin) et de complexité des preuves (aucun système de preuve optimal n’existe), l’article construit des prouveurs en un message pour NP/SAT, sans setup et avec solidité parfaite, qui obtiennent les conséquences falsifiables et basées sur des jeux du zéro connaissance propriété par propriété. Un prouveur unique couvrant toutes les propriétés « naturelles » de ce type est une extension supplémentaire, en partie conjecturale — et couvrir littéralement toutes les propriétés falsifiables est probablement impossible, parce que les preuves restent réutilisables. Le résultat est théorique et conditionnel, pas une primitive déployée, mais il montre une nouvelle façon d’utiliser l’improuvabilité en théorie des preuves comme ressource cryptographique.