Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption

Imaginez que vous envoyez un message secret à un ami, mais que vous devez l'envoyer via un bureau de poste tenu par un gobelin malicieux qui adore jeter un coup d'œil aux lettres. Autrefois, on enfermait la lettre dans une boîte, mais une fois que le gobelin l'ouvrait pour lire le message, le secret était perdu. Puis, une invention magique appelée Chiffrement Homomorphe est arrivée. C'est comme un coffre-fort spécial qui permet au gobelin d'effectuer des calculs sur les lettres verrouillées — les additionner, les multiplier, les trier — sans jamais les déverrouiller. Lorsque le gobelin vous rend le résultat, vous déverrouillez la boîte et vous obtenez la bonne réponse au problème mathématique, même si le gobelin n'a jamais vu les nombres à l'intérieur.

Cependant, il y a un piège. Dans la version la plus populaire de cette magie, appelée CKKS, les mathématiques ne sont pas parfaites. À cause de la complexité des nombres, le résultat que vous récupérez est légèrement « flou » ou approximatif, comme une photo de mauvaise qualité au lieu d'une image nette. Généralement, ce flou est sans importance ; c'est juste un tout petit peu de statique. Mais un gobelin sournois (un attaquant) peut demander la réponse à de nombreux problèmes mathématiques différents, comparer les résultats flous avec ce qu'il pense être la réponse, et utiliser ces infimes différences pour reconstruire lentement votre clé secrète. C'est comme si le gobelin pouvait déterminer exactement comment votre coffre-fort vacille lorsqu'on le secoue, et utilisait ce vacillement pour trouver la combinaison. Pour empêcher cela, les cryptographes ont inventé une défense appelée Inondation de Bruit (Noise Flooding) : on ajoute un énorme sursaut de statique aléatoire (du bruit) à la réponse avant de l'envoyer, noyant ainsi les petits indices que le gobelin tentait d'utiliser.

La grande question était : Combien de statique faut-il ajouter ? Si vous ajoutez trop peu, le gobelin pourra toujours déceler le secret. Si vous en ajoutez trop, la réponse devient tellement floue qu'elle est inutile. La partie délicate est que le gobelin peut poser des questions une par une, changeant sa stratégie en fonction de ses réponses précédentes. Si vous ajoutez de la statique pour chaque question séparément, le « coût » de la statique s'accumule rapidement, vous obligeant à rendre les réponses incroyablement floues. Mais une idée mathématique ingénieuse a suggéré que si l'on considère l'ensemble du jeu d'un coup, le coût pourrait croître beaucoup plus lentement — comme la racine carrée du nombre de questions, plutôt que le nombre lui-même. Ce document porte sur la preuve que cette idée ingénieuse fonctionne réellement, et sur la preuve, d'une manière qu'un ordinateur peut vérifier à chaque étape, qu'aucune erreur n'a été commise.

---

La Grande Découverte du Papier : Le Secret « Pythagoricien »

Ce document, intitulé « Verified Pythagorean Composition for Adaptive Cryptographic Games », est un accomplissement majeur de la vérification formelle, qui consiste essentiellement à utiliser un ordinateur super intelligent pour vérifier les erreurs dans les preuves mathématiques. Les auteurs, une équipe de chercheurs, ont pris un argument de sécurité célèbre concernant l'inondation de bruit et l'ont traduit dans un langage compréhensible par l'ordinateur. Ils ont ensuite demandé à l'ordinateur de vérifier chaque étape logique, s'assurant que les mathématiques tiennent bon sous l'examen le plus intense.

Leur travail central est une nouvelle façon de penser à la manière dont les erreurs s'accumulent lorsque vous avez un attaquant sournois posant de nombreuses questions.

Le Problème de la « Photo Floue »

Imaginez que vous essayiez de cacher un secret en ajoutant un peu de statique à une photo. Si vous ajoutez un tout petit peu de statique, la photo reste claire, mais un gobelin à l'œil aiguisé pourrait repérer le secret. Si vous ajoutez beaucoup de statique, le secret est en sécurité, mais la photo est maintenant un désastre.
Dans le monde du chiffrement, la « statique » est appelée bruit. Le document examine un scénario où un attaquant demande le résultat déchiffré d'un message jusqu'à $q$ fois. Chaque fois, le défenseur ajoute du bruit pour cacher le secret.

• L'Ancienne Méthode (Perte Linéaire) : Si vous traitez chaque question comme un événement distinct, vous devez ajouter assez de bruit pour être en sécurité pour chaque question. Si l'attaquant pose 100 questions, vous pourriez avoir besoin de 100 fois plus de bruit, rendant le résultat final totalement inutile.
• La Nouvelle Méthode (Perte en Racine Carrée) : Le document confirme une stratégie plus intelligente. Il montre que parce que les questions de l'attaquant sont liées (elles sont « adaptatives »), la quantité totale de bruit nécessaire ne croît que par la racine carrée du nombre de questions ($\sqrt{q}$). Ainsi, pour 100 questions, vous n'avez besoin que de 10 fois plus de bruit, et non de 100. C'est une victoire majeure car cela signifie que vous pouvez garder les réponses beaucoup plus claires tout en restant en sécurité.

L'Analogie « Pythagoricienne »

Pourquoi l'appellent-ils « Pythagoricien » ? Pensez à un triangle rectangle. Si vous avez deux côtés de longueur 3 et 4, le côté le plus long (l'hypoténuse) n'est pas $3 + 4 = 7$. C'est $\sqrt{3^2 + 4^2} = 5$. La longueur totale est plus courte que la simple addition des côtés.
Dans ce document, les « côtés » sont les minuscules portions de risque (ou de « coût ») provenant de chacune des questions de l'attaquant.

• L'Erreur : Si vous additionnez simplement les risques ($3 + 4$), vous obtenez un nombre énorme et effrayant.
• La Réalité : Les auteurs prouvent que ces risques se combinent comme les côtés d'un triangle. Ils se « compensent » un peu parce qu'ils sont liés. Le risque total est la racine carrée de la somme des carrés.
  Le document prouve que vous pouvez suivre ces risques séparément (sous forme de « coûts de Kullback-Leibler conditionnels », une façon mathématique élégante de dire « à quel point les réponses semblent différentes ») et ne les convertir en un « score de sécurité » final qu'à la toute fin. Cela permet aux mathématiques de rester efficaces et au bruit de rester faible.

Le Rôle de l'Ordinateur : Le « Avocat Robot »

Vous pourriez vous demander : « Pourquoi avons-nous besoin d'un ordinateur pour vérifier cela ? Les mathématiques ne sont-elles pas simplement des mathématiques ? »
Le problème est que ces preuves sont incroyablement complexes. Elles impliquent des milliers d'étapes, traitant des probabilités, des nombres aléatoires et le comportement d'un attaquant sournois qui change d'avis. Il est facile pour un humain de manquer un détail infime ou de faire une petite hypothèse qui brise tout l'argument.
Les auteurs ont utilisé un outil appelé Rocq (un assistant de preuve) et une bibliothèque appelée SSProve. Ils n'ont pas seulement écrit la preuve sur papier ; ils ont construit un modèle numérique du jeu de chiffrement.

1. La Logique : Ils ont créé un nouvel ensemble de règles (une « logique de programme ») qui indique à l'ordinateur comment gérer ces combinaisons de risques « pythagoriciennes ».
2. Le Compilateur : Ils ont construit un « compilateur de trace », qui est comme un robot qui surveille le programme de l'attaquant. Il peut mettre l'attaquant en pause, observer son prochain mouvement, puis le laisser continuer, tout en gardant le secret en sécurité.
3. La Vérification : L'ordinateur a vérifié chaque ligne de code et chaque étape mathématique. Il a confirmé que si le chiffrement sous-jacent est sécurisé, alors l'ajout de cette défense d'inondation de bruit le rend sécurisé contre ces types spécifiques d'attaques, avec l'efficacité de la « racine carrée ».

Ce que cela signifie pour vous

Le document n'invente pas une nouvelle méthode de chiffrement ni une nouvelle attaque. Au lieu de cela, il prend une défense connue (l'inondation de bruit) et prouve, avec une certitude mathématique absolue, qu'elle fonctionne exactement comme la théorie ingénieuse de la « racine carrée » le prédisait.

• Il écarte l'idée que vous devez ajouter une quantité massive de bruit (croissance linéaire) pour rester en sécurité face à des attaquants adaptatifs.
• Il prouve que la croissance en « racine carrée » est réelle et sûre, à condition que le chiffrement sous-jacent soit déjà sécurisé.
• Il confirme que les mathématiques complexes derrière cette défense ne comportent pas de failles cachées.

Les auteurs précisent avec prudence qu'il s'agit d'une preuve vérifiée de la logique, et non d'une garantie que chaque logiciel de chiffrement spécifique au monde est parfait. Ils ont prouvé que si vous avez un bon schéma de chiffrement et que vous appliquez correctement cette inondation de bruit, les mathématiques disent que vous êtes en sécurité. Ils ont également noté qu'ils n'ont pas vérifié les détails spécifiques du schéma de chiffrement le plus populaire (CKKS) lui-même, mais seulement la logique de la défense par le bruit. Cependant, pour les défenseurs de la confidentialité numérique, c'est une étape majeure : cela signifie que nous pouvons faire confiance aux mathématiques qui protègent nos secrets, même lorsque les attaquants sont intelligents et persistants.

En résumé, ce document est comme un maître architecte qui, après des années de débat, fait enfin appel à une équipe d'inspecteurs robots pour confirmer que la conception du pont est solide. Ils ont prouvé que le pont n'a pas besoin d'être construit avec deux fois plus d'acier que prévu ; la géométrie ingénieuse de la conception (la règle pythagoricienne) est suffisante pour supporter le poids, gardant le chemin dégagé et les secrets cachés.