Non-Trivial Zero-Knowledge Implies One-Way Functions

1. Problématique et Contexte

Le problème fondamental :
La cryptographie moderne repose sur l'existence de primitives de base, notamment les Fonctions à Sens Unique (OWF - One-Way Functions). Une question centrale, initiée par Ostrovsky et Wigderson, consiste à déterminer quelles sont les hypothèses minimales nécessaires pour construire des systèmes de preuves à divulgation nulle de connaissance (ZK - Zero-Knowledge).

Des travaux récents (Hirahara et Nanashima, STOC'2024) ont établi que si $NP \not\subseteq ioP/poly$ (c'est-à-dire si NP n'est pas soluble en temps polynomial avec conseils de manière infiniment souvent), alors l'existence de preuves ZK pour NP avec des erreurs négligeables implique l'existence d'OWF.

Le vide théorique :
Cependant, les techniques existantes échouent lorsque les erreurs de sécurité (complétude, soundness, et zero-knowledge) sont non négligeables (c'est-à-dire constantes ou grandes).

• Si la somme des erreurs $\varepsilon_c + \varepsilon_s + \varepsilon_{zk} \ge 1$, un protocole ZK trivial existe sans aucune hypothèse cryptographique (en choisissant aléatoirement entre rejeter, accepter, ou révéler le témoin).
• La question ouverte était : Les protocoles ZK "non triviaux" (où $\varepsilon_c + \varepsilon_s + \varepsilon_{zk} < 1$) avec des erreurs constantes impliquent-ils l'existence d'OWF ?

2. Méthodologie et Approche Technique

Les auteurs proposent une caractérisation complète de la complexité dans le pire des cas pour les protocoles ZK non triviaux. Leur approche repose sur une généralisation des techniques de réduction existantes (Universal Extrapolation) pour surmonter les barrières liées aux grandes erreurs.

A. Le Cas Non-Interactif (NIZK)

Pour les preuves non interactives, les auteurs utilisent une technique de répétition pour contourner les limitations des analyses précédentes (Ostrovsky-Wigderson, Chakraborty et al.).

• Le problème des anciennes techniques : Elles échouent car un simulateur peut produire des preuves "bonnes" (acceptées) et "mauvaises" (rejetées) de manière aléatoire, rendant la distinction difficile si les erreurs sont grandes.
• La solution (Répétition) : L'algorithme de décision $A$ génère un CRS (Common Reference String) et exécute le simulateur de nombreuses fois ($p(|x|)$ fois) avec le même CRS mais de nouvelles randomisations.
  • Si $x \notin L$, la probabilité d'acceptation reste bornée par l'erreur de soundness $\varepsilon_s$.
  • Si $x \in L$, si le CRS est "bon" (le simulateur a une probabilité non négligeable de produire une preuve acceptée), la répétition garantit qu'au moins une preuve sera acceptée avec une probabilité élevée ($1 - \varepsilon_{zk}$).
  • Cela permet de construire un algorithme qui distingue $L$ de son complément avec un avantage significatif tant que $\varepsilon_s + \varepsilon_{zk} < 1$.

B. Le Cas Interactif (ZK Public-Coin)

Généraliser cela aux protocoles interactifs est plus complexe car le vérificateur a un état interne et plusieurs tours.

• Proveur Malveillant ($\tilde{P}$) : Les auteurs définissent un proverbe malveillant qui, à chaque tour, essaie de choisir le message qui maximise la probabilité d'acceptation future.
• Estimation de la probabilité : Comme le calcul exact est impossible, $\tilde{P}$ utilise l'Extrapolation Universelle (UE) pour échantillonner de nombreux messages possibles et choisir le "meilleur" parmi eux.
• Gestion des tours : Pour les protocoles à nombre constant de tours ($k$), l'algorithme simule l'interaction entre $\tilde{P}$ et le vérificateur. L'analyse montre que si le protocole est à divulgation nulle, le proverbe malveillant ne peut pas être significativement moins performant que le proverbe honnête, sauf si la somme des erreurs est proche de 1.
• Cas des pièces privées (Private-Coin) : Si le protocole utilise des pièces privées, les auteurs montrent que soit des OWF à entrée auxiliaire existent, soit le protocole peut être converti en un protocole public-coin équivalent.

3. Résultats Principaux

Sous l'hypothèse que $NP \not\subseteq ioP/poly$, les auteurs établissent les théorèmes suivants :

1. Théorème Principal (NIZK) : L'existence de preuves NIZK non triviales (où $\varepsilon_c + \varepsilon_s + \varepsilon_{zk} < 1 - 1/poly$) pour NP implique l'existence de Fonctions à Sens Unique (OWF).
2. Théorème Principal (Interactif) : L'existence de preuves ZK interactives non triviales, à nombre constant de tours et à pièces publiques (public-coin), pour NP implique l'existence de OWF.
3. Cas des pièces privées : L'existence de protocoles ZK non triviaux à pièces privées implique l'existence de OWF à entrée auxiliaire (auxiliary-input OWF).

Amélioration par rapport aux travaux antérieurs :
Ces résultats dépassent les limitations de [CHK25], qui nécessitaient des conditions plus strictes sur les erreurs (ex: $\varepsilon_{zk} + \sqrt{\varepsilon_s} < 1$). Les auteurs montrent que la seule condition nécessaire est que la somme des erreurs soit strictement inférieure à 1 (régime non trivial).

4. Applications : Amplification

Un résultat clé de l'article est l'application de ces théorèmes à l'amplification des protocoles ZK.

• Problème : Peut-on transformer un protocole ZK avec des erreurs constantes (mais non triviales) en un protocole standard avec des erreurs négligeables ?
• Solution :
  • Si $NP \subseteq BPP$, les protocoles ZK triviaux existent déjà.
  • Si $NP \not\subseteq ioP/poly$, les théorèmes ci-dessus garantissent l'existence d'OWF à partir du protocole ZK non trivial.
  • Une fois les OWF obtenues, on peut utiliser des théorèmes d'amplification existants (comme [BG24, AK25] pour le NIZK et [BJY97] pour l'interactif) pour construire des protocoles ZK standards avec des erreurs négligeables.
• Corollaire : Sous des hypothèses de complexité très faibles, l'existence de n'importe quel protocole ZK non trivial (même avec de grandes erreurs) implique l'existence de protocoles ZK standards (avec erreurs négligeables).

5. Signification et Impact

• Clôture d'une question ouverte : Ce travail comble un vide majeur dans la compréhension de la complexité des preuves ZK. Il démontre qu'il n'y a pas de "zone grise" : soit les protocoles ZK sont triviaux (somme des erreurs $\ge 1$) et n'impliquent rien, soit ils sont non triviaux et impliquent la cryptographie de base (OWF).
• Robustesse des hypothèses : Il montre que la construction d'OWF ne nécessite pas de protocoles ZK parfaits ou à erreurs négligeables dès le départ. Même des protocoles faibles, s'ils sont non triviaux, suffisent à engendrer la cryptographie.
• Implications pour la sécurité : Cela renforce la croyance que la sécurité des protocoles ZK est intrinsèquement liée à la difficulté computationnelle sous-jacente. Si l'on parvenait à construire un protocole ZK non trivial pour un problème difficile sans OWF, cela contredirait les hypothèses de complexité standard ($NP \not\subseteq ioP/poly$).

En résumé, cet article établit que la non-trivialité d'un protocole ZK est une condition suffisante pour dériver des fonctions à sens unique, transformant ainsi une propriété de complexité (l'existence d'un protocole avec des erreurs bornées) en une primitive cryptographique fondamentale.