Résumé Technique : Le Monde de l'Observateur

1. Énoncé du Problème

Les cinq mondes d'Impagliazzo (Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania) fournissent un cadre fondamental pour raisonner sur l'existence des primitives cryptographiques et sur l'écart entre la complexité du pire cas et celle du cas moyen. Cependant, ce cadre repose sur une « hypothèse silencieuse » qui n'a jamais été explicite : que chaque partie, y compris l'adversaire, observe la chaîne d'entrée complète $x$ (c'est-à-dire que l'observateur est la fonction identité $O_\top$).

Cette hypothèse traite la capacité d'observation d'un adversaire comme une constante, ignorant la possibilité qu'un adversaire puisse être structurellement contraint de ne voir qu'une projection de l'entrée (par exemple, des comptages de symboles, des parités ou une longueur). Par conséquent, le cadre des cinq mondes ne peut pas exprimer les phénomènes où l'incapacité de l'adversaire à distinguer les entrées provient d'un aveuglement observationnel plutôt que d'une dureté computationnelle. Le document identifie la nécessité de relâcher l'hypothèse $O = O_\top$ et d'introduire un second axe, orthogonal à l'axe de la complexité : l'axe observationnel, défini par la hiérarchie des observateurs canoniques.

2. Méthodologie

Le document étend le cadre théorique d'Impagliazzo en intégrant la « théorie de l'observateur » établie dans des travaux antérieurs [9]. La méthodologie consiste en :

1. Formalisation de la Hiérarchie des Observateurs : Utilisation d'un ordre partiel d'observateurs $O: \Sigma^* \to S$, où un observateur est une application de prétraitement fixe appliquée à l'entrée avant tout début de calcul par une machine. Les observateurs canoniques clés incluent :

   • $O_\top$ : Identité (information complète).
   • $O_{prof}$ : Profil (comptages de symboles, ex: $(|x|_0, |x|_1)$).
   • $O_\perp$ : Application constante (rejette toute information).
   • $O_{len}, O_{par}, O_k$ : Longueur, parités et sous-séquences $k$, respectivement.

2. Construction de la Table Monde-Observateur : Création d'un paysage bidimensionnel où les lignes représentent les cinq mondes d'Impagliazzo (hypothèses computationnelles) et les colonnes représentent les observateurs canoniques (contraintes observationnelles).

3. Définition du Monde de l'Observateur ($W_O$) : Définition formelle d'un nouveau paysage où l'adversaire opère sous un observateur contraint $O$ tandis que le défenseur conserve un accès total ($O_\top$). Cela modélise des scénarios cryptographiques où l'adversaire ne voit que des textes chiffrés ou des informations partielles.

4. Extension Paramétrique ($W_O^\varepsilon$) : Introduction d'une famille de mondes où l'invariant observationnel est partiellement violé par un paramètre $\varepsilon \in [0, 1]$, modélisant des adversaires qui récupèrent une partie de l'information rejetée via des oracles, des canaux auxiliaires ou des fuites structurelles.

5. Instanciation Physique : Mise en correspondance des propriétés mathématiques de la hiérarchie observationnelle avec les limites physiques, incluant les coûts thermodynamiques (principe de Landauer), les transitions de mesure quantique et les limites d'information cosmologiques (bornes de Bekenstein et de Margolus-Levitin).

3. Contributions Clés et Résultats

A. L'Effondrement Structurel Inconditionnel

Le document prouve que pour l'observateur canonique $O_{prof}$ (profil), les classes de complexité s'effondrent inconditionnellement :
$$P^{O_{prof}} = NP^{O_{prof}} \subsetneq P$$
Ce résultat est valable dans les cinq mondes simultanément, indépendamment de savoir si $P=NP$ ou si des fonctions à sens unique existent.

• Signification : Cela démontre que la distinction entre dureté computationnelle et aveuglement structurel est réelle et indépendante. Un problème peut être computationnellement facile (dans $P$) mais indécidable pour un adversaire contraint par $O_{prof}$ simplement parce que le problème dépend de l'ordre des symboles, que $O_{prof}$ rejette.

B. La Table Monde-Observateur et les Cellules Étiquetées

Le document classifie les interactions entre les mondes computationnels et les contraintes observationnelles, identifiant quatre « cellules étiquetées » spécifiques qui révèlent des phénomènes cryptographiques invisibles dans le cadre standard des cinq mondes :

• Cellule (a) (Tout Monde $\times O_{prof}$) : Même dans Algorithmica ($P=NP$), l'effondrement observationnel $P^{O_{prof}} \subsetneq P$ persiste. La puissance de calcul ne peut surmonter l'aveuglement structurel.
• Cellule (b) (Pessiland $\times O_{prof}$) : Dans Pessiland, où les problèmes NP sont difficiles en moyenne mais où aucune fonction à sens unique n'existe, un adversaire $O_{prof}$ fait face à une double limitation : la dureté du cas moyen et l'aveuglement structurel à l'ordre. Ces limitations sont indépendantes ; l'adversaire ne peut même pas reconnaître les problèmes dépendant de l'ordre comme étant distincts des problèmes triviaux.
• Cellule (c) (Minicrypt $\times O_{prof}$) : Dans Minicrypt, où les fonctions à sens unique (OWF) existent, le document prouve une borne inférieure structurelle : toute OWF doit être sensible à l'ordre des symboles d'entrée. Toute fonction invariante par permutation (ex: poids de Hamming) ne peut pas être à sens unique, même dans Minicrypt. C'est une conséquence de la structure observationnelle, et non des hypothèses computationnelles.
• Cellule (d) (Cryptomania $\times O_\perp$) : Dans Cryptomania, un adversaire avec $O_\perp$ (ne voyant rien) ne peut récupérer aucune information sur le texte clair, quelle que soit l'existence de la cryptographie à clé publique. Cela modélise la sécurité parfaite des schémas comme le Masque à Usage Unique à Base Mixte (MR-OTP), où la sécurité est informationnelle, et non computationnelle.

C. Le Monde de l'Observateur ($W_O$) comme Sixième Paysage

Le document définit le Monde de l'Observateur comme un sixième paysage qui n'est pas réductible aux cinq originaux.

• Orthogonalité : L'axe observationnel est orthogonal à l'axe computationnel. Aucune hypothèse computationnelle n'implique l'effondrement structurel, et aucune contrainte observationnelle n'implique une hypothèse computationnelle spécifique (ex: $P \neq NP$).
• Asymétrie : Le cadre modélise explicitement l'asymétrie entre le défenseur (qui voit $x$) et l'adversaire (qui voit $O(x)$).

D. Famille Paramétrique $W_O^\varepsilon$ et la Cellule « La Plus Riche Informationnellement »

Le document introduit $W_O^\varepsilon$ pour modéliser les violations partielles des invariants observationnels.

• Résultat : La cellule (Pessiland, $O_{prof}$, $\varepsilon > 0$) est identifiée comme la cellule « la plus riche informationnellement » (et donc la plus peu sûre). Dans ce monde :
  1. Les problèmes NP sont difficiles en moyenne (Pessiland).
  2. L'adversaire est structurellement aveugle à l'ordre ($O_{prof}$).
  3. L'adversaire a partiellement brisé cet aveuglement ($\varepsilon > 0$), récupérant l'information d'ordre.
  4. Aucune fonction à sens unique n'existe.
     Ici, la sécurité computationnelle, la sécurité d'invariance et la sécurité observationnelle échouent toutes simultanément.

E. Connexions Physiques (Problèmes Ouverts)

Le document relie le cadre à la théorie physique, proposant trois problèmes ouverts :

1. Thermodynamique : Les observateurs adaptatifs (ceux faisant des requêtes basées sur des réponses précédentes) incorrent un coût de Landauer ($k_B T \ln 2$ par bit effacé). La profondeur d'un observateur adaptatif correspond à un coût thermodynamique.
2. Mécanique Quantique : La mesure quantique est modélisée comme une transition d'un niveau inférieur à un niveau supérieur dans la hiérarchie observationnelle (de la superposition/$O_\perp$ à une valeur définie). La décohérence correspond à une transition descendante.
3. Cosmologie : La borne de Bekenstein ($\approx 10^{122}$ bits) et la borne de Margolus-Levitin ($\approx 10^{121}$ opérations) imposent un plafond fini à l'observateur physiquement réalisable $O_{phys}^\top$. Le document note que la coordonnée temporelle de l'univers ne nécessite que $\approx 203$ bits pour être indexée, mais porte tout l'ordre causal, soulignant une asymétrie entre le coût informationnel et le rôle structurel.

4. Signification et Revendications

Le document affirme que le cadre des cinq mondes est insuffisant car il décrit des variations le long d'une seule ligne (la dureté computationnelle) tout en laissant l'axe observationnel fixe. En introduisant le Monde de l'Observateur, le document fournit un langage unifié pour modéliser les adversaires en cryptographie qui sont contraints non seulement par le calcul, mais par ce qu'ils peuvent observer.

• Indépendance : Le résultat central est que l'aveuglement observationnel et la dureté computationnelle sont des phénomènes indépendants. L'effondrement structurel $P^{O_{prof}} = NP^{O_{prof}} \subsetneq P$ tient de manière inconditionnelle, prouvant que la « dureté » est relative à l'information de l'observateur.
• Intuition Cryptographique : Le cadre révèle que certaines propriétés cryptographiques (comme la nécessité de la sensibilité à l'ordre pour les OWF ou la sécurité parfaite du MR-OTP) sont des conséquences structurelles de la hiérarchie des observateurs, indépendamment de savoir si $P=NP$ ou si des fonctions à sens unique existent.
• Modestie : L'auteur précise explicitement que les connexions avec la physique (thermodynamique, quantique, cosmologie) sont énoncées comme des problèmes ouverts et des conjectures, et non comme des théorèmes. L'auteur, un informaticien, ne prétend pas avoir résolu des problèmes physiques, mais propose un vocabulaire mathématique pour formaliser la relation entre les hiérarchies observationnelles et les limites physiques.

Le document conclut que le Monde de l'Observateur est une extension nécessaire du paysage de la complexité, capturant la dimension du « ce que l'adversaire voit » qui était auparavant implicite et non analysée.