💻 computer science

Weak Zero-Knowledge and One-Way Functions

Cet article démontre que l'existence de protocoles Zero-Knowledge faibles pour les langages NP difficiles dans le pire des cas, sous des conditions d'erreurs spécifiques, implique l'existence de fonctions à sens unique.

Auteurs originaux : Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

Publié 2026-02-19

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le Secret des Verrous et des Miroirs : Une Histoire de Cryptographie

Imaginez que vous êtes un gardien de musée (le Vérificateur) et qu'un visiteur (le Preuveur) prétend connaître le code secret pour ouvrir une vitrine contenant un trésor. Le visiteur veut vous prouver qu'il connaît le code sans jamais vous le dire. C'est ce qu'on appelle un protocole à Zéro Connaissance (Zero-Knowledge).

Dans un monde idéal, ce visiteur serait parfait : il ne se tromperait jamais, et vous ne pourriez jamais deviner le code en regardant sa démonstration. Mais dans la réalité, les protocoles que nous utilisons aujourd'hui ne sont pas parfaits. Ils ont des erreurs :

Erreur de Complétude ( $\epsilon_c$ ) : Parfois, le visiteur honnête se trompe et échoue, même s'il connaît le code.
Erreur de Sonorité ( $\epsilon_s$ ) : Parfois, un imposteur arrive à tromper le gardien et à ouvrir la vitrine sans connaître le code.
Erreur de Zéro Connaissance ( $\epsilon_z$ ) : Parfois, en regardant la démonstration, le gardien apprend un petit bout du code secret.

Jusqu'à présent, les mathématiciens pensaient que pour que ces protocoles soient utiles et sûrs, ces erreurs devaient être infimes (presque nulles). Ce papier de recherche (par Rohit Chatterjee, Yunqi Li et Prashant Nalini Vasudevan) change la donne. Il dit : "Et si les erreurs étaient grandes ? Et si le visiteur se trompait souvent ?"

La Grande Question : Un Verrou Faible peut-il créer une Forteresse ?

Le but ultime de la cryptographie est de créer des Fonctions à Sens Unique (One-Way Functions).

L'analogie : Imaginez un hachoir à viande. C'est très facile de mettre un steak dedans et d'obtenir de la viande hachée (c'est facile). Mais c'est impossible de prendre la viande hachée et de reconstituer le steak d'origine (c'est difficile).
En cryptographie, ces "hachoirs" sont essentiels pour sécuriser nos emails, nos banques et nos données.

La question centrale de ce papier est : Si nous avons des protocoles de "Zéro Connaissance" imparfaits (avec des erreurs notables), cela suffit-il à prouver que ces "hachoirs" mathématiques existent vraiment ?

Les Découvertes : Des Miroirs qui Réfléchissent Mieux

Les auteurs ont découvert que OUI, même avec des protocoles imparfaits, nous pouvons construire ces verrous mathématiques solides, à condition que la somme des erreurs ne dépasse pas une certaine limite.

Voici leurs trois découvertes principales, expliquées simplement :

1. Le Cas "Sans Interaction" (NIZK)

Imaginez un protocole où le visiteur envoie un seul message (un ticket) et le gardien décide tout de suite.

L'ancienne règle : Il fallait que la somme des erreurs soit très petite, ou qu'une erreur spécifique (l'erreur de l'imposteur) soit réduite par une racine carrée (une astuce mathématique compliquée).
La nouvelle règle : Les auteurs montrent que tant que la somme totale des erreurs ( $\epsilon_c + \epsilon_s + \epsilon_z$ ) est inférieure à 1, on peut construire un "hachoir" mathématique.
L'analogie : Imaginez que vous avez un jeu de dés. Si la probabilité que le visiteur triche ou se trompe est inférieure à 100% (ce qui est toujours vrai si la somme est < 1), vous pouvez utiliser ce jeu pour créer un verrou impossible à ouvrir sans la clé. Ils ont éliminé les règles trop strictes précédentes.

2. Le Cas "Public Coin" (Plusieurs tours)

Maintenant, imaginez un jeu de rôle où le gardien et le visiteur échangent plusieurs messages. Le gardien lance des dés publics (des nombres aléatoires) et le visiteur répond.

La découverte : Si le nombre de tours est $t$ , la condition pour créer un verrou sûr est que la somme des erreurs soit inférieure à 1, en tenant compte du nombre de tours. Plus il y a de tours, plus la tolérance aux erreurs de "Zéro Connaissance" est stricte, mais la formule est plus simple et plus générale que ce qu'on pensait avant.

3. Le Cas "Tours Constants" (Un nombre fixe de tours)

Si le jeu ne dure qu'un nombre fixe de tours (par exemple, 3 ou 4 échanges), les auteurs ont trouvé une condition encore plus permissive.

Le résultat : Même si les erreurs sont un peu plus grandes, on peut prouver l'existence de verrous mathématiques qui fonctionnent "presque toujours" (une notion appelée "infinitely often"). C'est comme dire : "Même si le hachoir casse parfois, il fonctionne assez souvent pour être utile."

Comment ont-ils fait ? (La Magie de la Réduction)

Comment passer d'un protocole imparfait à un verrou parfait ?
Les auteurs utilisent une technique appelée réduction.

L'analogie du Détective : Imaginez que vous soupçonnez un visiteur d'être un imposteur. Vous lui donnez un défi : "Si vous pouvez inverser ce processus mathématique (retrouver le steak haché), alors vous êtes un imposteur."
Si le visiteur réussit à inverser le processus, cela signifie qu'il a trouvé une faille dans le protocole de Zéro Connaissance.
Les auteurs montrent que si un tel visiteur existe, alors le protocole de Zéro Connaissance ne protège plus vraiment le secret.
Le retournement : Si le protocole de Zéro Connaissance est vraiment sûr (même avec des erreurs), alors personne ne peut inverser le processus. Donc, le processus est un "hachoir" (Fonction à Sens Unique).

Ils ont amélioré cette logique en intégrant la vérification directement dans le processus de "hachage". Au lieu de vérifier deux fois (ce qui double l'erreur), ils vérifient une seule fois de manière intelligente, ce qui leur permet d'accepter des erreurs plus grandes.

Pourquoi est-ce important ?

Plus de flexibilité : Cela signifie que nous n'avons pas besoin de protocoles parfaits (qui sont très difficiles à construire) pour sécuriser nos systèmes. Des protocoles "moyens" ou "imparfaits" suffisent.
Théorie fondamentale : Cela renforce notre compréhension de la cryptographie. Nous savons maintenant que la sécurité (les verrous) est intrinsèquement liée à la capacité de cacher des secrets, même si cette capacité n'est pas parfaite.
Avenir : Cela ouvre la porte à de nouveaux protocoles plus rapides et plus simples, car nous n'avons plus besoin de "nettoyer" toutes les erreurs mathématiques avant de pouvoir les utiliser.

En Résumé

Ce papier nous dit : "Ne soyez pas trop exigeants avec vos serrures."
Même si votre système de preuve de secret a des failles, des erreurs de calcul ou des fuites d'information mineures, cela suffit à prouver que des verrous mathématiques inviolables existent. Les auteurs ont affiné les règles du jeu pour montrer que la sécurité est plus robuste et plus accessible que nous ne le pensions.

C'est une victoire pour la théorie cryptographique : elle nous dit que la perfection n'est pas nécessaire pour la sécurité ; l'imperfection contrôlée suffit à bâtir des forteresses.

1. Problématique

L'article s'intéresse à la relation fondamentale entre les protocoles Zero-Knowledge (ZK) et l'existence de Fonctions à Sens Unique (OWF - One-Way Functions).

Contexte : Il est bien établi que l'existence de protocoles ZK pour des langages difficiles (dans le pire des cas) implique l'existence de OWF. Cependant, les résultats antérieurs (notamment Ostrovsky-Wigderson [OW93] et Hirahara-Nanashima [HN24]) supposent généralement que les erreurs du protocole (complétude $\epsilon_c$ , soundness $\epsilon_s$ , et zero-knowledge $\epsilon_z$ ) sont négligeables.
Le défi : De nombreux protocoles ZK naturels et utiles (comme ceux pour le 3-coloriage ou l'isomorphisme de graphes) ont des erreurs qui ne sont pas négligeables, mais constantes ou polynomiales. On les appelle des protocoles de ZK Faible.
Question centrale : L'existence de protocoles ZK faibles pour tous les langages de NP implique-t-elle l'existence de OWF ? Si oui, sous quelles conditions précises sur les paramètres d'erreur ( $\epsilon_c, \epsilon_s, \epsilon_z$ ) ?

Des travaux récents (Chakraborty et al., [CHK25]) ont fait des progrès en montrant que si $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ , alors des OWF existent. Cependant, cette condition est restrictive et ne couvre pas tous les cas non triviaux.

2. Méthodologie

Les auteurs développent une nouvelle approche de réduction pour construire des fonctions à sens unique à partir de protocoles ZK faibles. Leur méthode repose sur plusieurs idées clés :

A. Construction de Fonctions à Entrée Auxiliaire (ai-OWF)

L'approche classique (Ostrovsky-Wigderson) consiste à définir une fonction $f_x$ basée sur un simulateur ZK. Si cette fonction est inversible, on peut construire un distinguisher qui décide le langage, contredisant sa difficulté.

Amélioration de la condition d'erreur : Les auteurs observent que la méthode classique pénalise l'erreur de zero-knowledge ( $\epsilon_z$ ) deux fois (une fois pour la simulation, une fois pour la vérification).
Nouvelle construction : Ils intègrent directement la procédure de vérification $V$ $V$ dans la définition de la fonction candidate. Au lieu de sortir $(r, \pi)$ $(r, π)$ , la fonction sort $(r, a)$ $(r, a)$ où $a = V(x; r, \pi)$ $a = V (x; r, π)$ .
- Cela permet de restreindre l'inverseur à trouver un pré-image correspondant à une preuve valide.
- Résultat : Pour les protocoles NIZK (Non-Interactive), la condition devient $\epsilon_c + \epsilon_s + \epsilon_z < 1$ (au lieu de $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ ).

B. Protocoles Public-Coin Multi-tours

Pour les protocoles interactifs où le vérificateur envoie des bits aléatoires publics :

Approche récursive : Pour un protocole à $k$ tours, les auteurs définissent une séquence de fonctions $f_{k,x}, f_{k-1,x}, \dots, f_{1,x}$ .
Stratégie de l'attaquant : L'inversion d'une fonction $f_{i,x}$ est utilisée pour construire une stratégie de prover efficace pour le tour $i$ , qui maximise la probabilité d'acceptation des tours suivants.
Estimation de probabilité : Pour les protocoles à nombre constant de tours, ils utilisent des techniques d'estimation (basées sur la concentration de Hoeffding) pour approximer la probabilité d'acceptation conditionnelle, permettant d'affiner la borne d'erreur.

C. De la difficulté moyenne à OWF standard

Une fois des ai-OWF (Fonctions à sens unique avec entrée auxiliaire) établies, les auteurs utilisent des résultats de la littérature ([CHK25], [Yao82], [IL89]) pour :

Montrer que les ai-OWF impliquent l'existence de langages difficiles en moyenne (One-Sided Average-Case Hardness).
Utiliser les protocoles ZK faibles sur ces langages spécifiques pour construire des OWF standards.

3. Contributions et Résultats Principaux

Les auteurs établissent trois théorèmes principaux reliant les paramètres d'erreur des protocoles ZK à l'existence de OWF, sous l'hypothèse que NP n'est pas contenu dans $P/poly$ (ou $ioP/poly$).

Résultat 1 : NIZK (Non-Interactive)

Théorème : Si tous les langages de NP possèdent un protocole NIZK (ou argument) avec des erreurs satisfaisant $\epsilon_c + \epsilon_s + \epsilon_z < 1$ , alors des OWF existent.
Signification : Cela couvre toutes les valeurs non triviales possibles pour les erreurs. C'est une amélioration majeure par rapport à la condition précédente $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ .
Conséquence : Si $\epsilon_c$ est négligeable et que la somme des erreurs est $<1$ , alors on peut amplifier le protocole pour obtenir un NIZK avec toutes les erreurs négligeables.

Résultat 2 : Protocoles Public-Coin à $t$ messages

Théorème : Si tous les langages de NP possèdent un protocole ZK public-coin à $t$ messages satisfaisant $\epsilon_c + \epsilon_s + (t-1) \cdot \epsilon_z < 1$ , alors des OWF existent.
Note : La condition précédente aurait été $\epsilon_c + \epsilon_s + t \cdot \epsilon_z < 1$ . L'amélioration de $(t-1)$ à $t$ est obtenue grâce à la technique d'intégration de la vérification.

Résultat 3 : Protocoles Public-Coin à $k$ tours constants

Théorème : Si, pour une constante $k$ , tous les langages de NP possèdent un protocole ZK public-coin à $k$ tours satisfaisant $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ , alors des OWF "infinitely often" (ioOWF) existent.
Nuance : Pour ce cas, la preuve est non-black-box et aboutit à une sécurité "infinitely often" (valide pour une infinité de longueurs d'entrée) plutôt que pour toutes les longueurs. C'est une limitation de la méthode récursive actuelle.
Hypothèse : Ce résultat nécessite $NP \not\subseteq P/poly$ (plus fort que $ioP/poly$).

4. Signification et Impact

Complétude de la caractérisation : L'article résout presque complètement la question de savoir quand les protocoles ZK faibles impliquent des OWF. Il montre que la condition naturelle $\sum \text{erreurs} < 1$ est suffisante pour les NIZK, éliminant le besoin de conditions plus complexes comme la racine carrée de l'erreur de soundness.
Robustesse des primitives cryptographiques : Cela renforce la compréhension que la sécurité cryptographique (OWF) est intrinsèquement liée à la capacité de prouver des énoncés sans révéler d'information, même lorsque ces preuves sont imparfaites (erreurs constantes).
Limites et perspectives :
- Le résultat pour les protocoles à tours constants donne des ioOWF. Un problème ouvert est de savoir si l'on peut obtenir des OWF standards pour ces paramètres.
- L'extension aux protocoles à pièces privées (private-coin) reste une question ouverte.
- L'amélioration des paramètres d'erreur pour les protocoles à nombre de tours super-constant est également un défi.

En résumé, ce travail élargit considérablement le paysage théorique reliant la complexité computationnelle (difficulté des langages NP) à la cryptographie, en démontrant que même des protocoles Zero-Knowledge très faibles (avec des erreurs non négligeables) sont suffisants pour garantir l'existence de fonctions à sens unique, à condition que la somme de leurs erreurs reste strictement inférieure à 1.