💻 computer science

Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

Cet article établit une borne supérieure certifiée de $2^{-164,81}$ pour la probabilité d'échec de décapsulation honnête de ML-KEM-768 au sein d'une abstraction dépendante de l'oracle aléatoire et de la distribution binomiale centrée, en utilisant une analyse par couplage de graphes novatrice et des techniques d'anti-concentration exhaustives pour justifier rigoureusement l'échelle heuristique d'échec du schéma.

Auteurs originaux : Aurélie Duriez (netHsys SARL, Lille, France), Christophe Tommasini (Tommasini Conseil, Lille, France)

Publié 2026-09-10✓ Author reviewed ⓘ

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Aurélie Duriez (netHsys SARL, Lille, France), Christophe Tommasini (Tommasini Conseil, Lille, France)

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 par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Dans le monde numérique, la sécurité repose souvent sur des problèmes mathématiques qui sont faciles à utiliser dans un sens, mais extrêmement difficiles à inverser sans les bonnes informations secrètes. ML-KEM est un mécanisme d'établissement de clé post-quantique conçu pour rester sécurisé même contre les futurs ordinateurs quantiques. Comme d'autres systèmes cryptographiques basés sur les réseaux, il présente une probabilité extrêmement faible de ce que l'on appelle un échec de décapsulation honnête : même lorsque les deux parties se comportent correctement, les deux côtés pourraient en principe dériver des clés différentes. Estimer la rareté de ce phénomène est une question de correction importante. Les analyses précédentes se sont largement appuyées sur des estimations heuristiques de l'échelle d'échec, tandis qu'obtenir une limite rigoureuse qui préserve les dépendances mathématiques pertinentes entre les différents termes d'erreur est considérablement plus difficile.

Une nouvelle étude menée par Aurélie Duriez et Christophe Tommasini s'attaque à ce problème en développant une analyse mathématique rigoureuse de ML-KEM-768 au sein d'une abstraction explicite de fonction aléatoire idéalisée / binomiale centrée, ou ROM/CBD. Ce travail n'est pas une simulation et ne tente pas de calculer le taux d'échec exact. Au lieu de cela, les auteurs dérivent une limite supérieure certifiée sur la probabilité d'un échec de décapsulation honnête tout en préservant les dépendances importantes entre les différents termes d'erreur. En particulier, l'analyse suit les dépendances induites par la matrice publique et par les deux termes de compression du texte chiffré plutôt que de simplement les traiter comme indépendants. La limite supérieure certifiée qui en résulte est inférieure à un sur 2 à la puissance 164,81.

Cette découverte est significative car elle remplace une estimation heuristique de l'échelle d'échec, au sein du modèle explicite étudié, par une limite supérieure certifiée tenant compte des dépendances. L'analyse ne suppose pas simplement que les erreurs pertinentes sont indépendantes ; elle préserve les dépendances mathématiques qui apparaissent entre elles. La limite certifiée atteint essentiellement la même échelle que les estimations heuristiques antérieures, mais cela ne doit pas être interprété comme la preuve que ces estimations sont la probabilité d'échec exacte. Le résultat est délibérément plus étroit : au sein de l'abstraction ROM/CBD explicite étudiée dans l'article, la probabilité d'un échec de décapsulation honnête est rigoureusement bornée par une valeur extrêmement petite. L'article précise également qu'il ne s'agit pas d'un taux d'échec de décapsulation exact et qu'il ne s'agit pas d'un énoncé informationnel sur l'instanciation fixe de SHAKE de la norme FIPS 203.

Le travail a nécessité une approche différente du problème. Les analyses heuristiques simplifiées peuvent devenir beaucoup plus faciles si certains termes d'erreur sont traités comme indépendants, mais la structure algébrique réelle crée des dépendances qu'une analyse rigoureuse doit préserver. Les auteurs ont donc développé une méthode qui suit ces dépendances tout au long du calcul au lieu de les écarter. Le processus de recherche a également utilisé une méthodologie assistée par l'IA pour explorer des approches candidates, identifier les cas critiques et structurer l'analyse. Cette utilisation exploratoire de l'IA a été combinée à des vérifications exhaustives vérifiées par ordinateur, une arithmétique exacte ou certifiée et des calculs vérifiables de manière indépendante pour clore les parties les plus difficiles de l'argument. Les affirmations mathématiques finales reposent donc sur des preuves explicites et reproductibles plutôt que sur la production de l'IA elle-même.

Le résultat est une limite de correction certifiée, rigoureuse et transparente, au sein de l'abstraction énoncée. Les chercheurs ont mis à disposition leur code, leurs données et les artefacts de support afin que les calculs puissent être vérifiés de manière indépendante. Ce niveau de reproductibilité est particulièrement important en cryptographie, où les affirmations mathématiques doivent être ouvertes à une vérification indépendante. L'étude montre que, dans l'abstraction ROM/CBD explicite considérée, la probabilité d'un échec de décapsulation honnête est bornée à un niveau extrêmement faible. Elle ne doit toutefois pas être interprétée comme un certificat général de sécurité pour ML-KEM-768, ni comme une preuve de toutes les propriétés de sécurité du schéma standardisé, ni comme un énoncé couvrant chaque implémentation matérielle ou logicielle.

Ce résultat fait progresser la compréhension rigoureuse d'un aspect spécifique de la correction de ML-KEM-768 en passant d'une estimation heuristique de l'échelle d'échec à une limite supérieure certifiée tenant compte des dépendances au sein d'une abstraction clairement définie. Il montre qu'une limite à l'échelle heuristique peut toujours être établie tout en préservant les dépendances importantes entre les termes d'erreur pertinents. Le nombre 164,81 est l'exposant certifié de cette limite supérieure : au sein de l'abstraction ROM/CBD énoncée, la probabilité d'échec de la décapsulation honnête est bornée au-dessus de 2 à la puissance -164,81. Ce chiffre doit donc être compris comme une propriété précise de la limite certifiée prouvée dans l'article, plutôt que comme une mesure générale de la sûreté ou de la sécurité de ML-KEM-768 dans son ensemble.

Les chercheurs ont également pris soin d'expliquer les limites de leur travail. Ils ont noté que leur preuve s'applique à une abstraction spécifique du système, et non nécessairement à chaque implémentation possible du logiciel. Ils n'ont pas prétendu avoir résolu le problème pour toutes les variations de la norme de chiffrement, ni suggéré que le système est immunisé contre tous les types d'attaques. Leur objectif portait strictement sur la correction du processus de déchiffrement dans des conditions honnêtes. En étant clairs sur ce qu'ils ont prouvé et sur ce qu'ils n'ont pas prouvé, ils se sont assurés que leurs conclusions ne soient pas mal interprétées. L'étude témoigne de la puissance d'une analyse minutieuse et détaillée dans un domaine où de petites erreurs peuvent avoir de lourdes conséquences. Elle montre qu'avec suffisamment de rigueur et les bons outils, même les systèmes mathématiques les plus complexes peuvent être compris et vérifiés.

En fin de compte, l'article livre un résultat précis mais délibérément limité : au sein de l'abstraction ROM/CBD énoncée, la probabilité de déchiffrement honnête est rigoureusement bornée par 2 à la puissance -164,81. Il s'agit d'une limite supérieure certifiée extrêmement petite, mais ce n'est pas un taux d'échec exact et ce n'est pas une preuve globale que le système ML-KEM-768 complet déployé fonctionne sans échec dans toutes les conditions réelles. La contribution réside dans le remplacement d'une estimation heuristique de l'échelle d'échec par une limite reproductible, vérifiable de manière indépendante et tenant compte des dépendances à l'intérieur d'un modèle clairement défini. Sa force ne vient pas de la prétention à une certitude au-delà de ce modèle, mais de l'explicitation de ce qui a été prouvé et de ce qui reste en dehors de la portée du résultat.

Résumé Technique : Bornes de correction pour ML-KEM-768 dépendantes des dépendances sous l'abstraction ROM/CBD

Énoncé du Problème
ML-KEM-768, standardisé dans la FIPS 203, présente une probabilité non nulle qu'un ciphertext généré honnêtement déchiffre un message différent de celui encapsulé (un échec de déchiffrement). Bien que la FIPS 203 rapporte une échelle d'échec heuristique d'environ $2^{-164,8}$ , cette valeur repose sur des modèles simplifiés qui supposent souvent l'indépendance entre les erreurs de compression et le bruit de réseau. Les analyses formelles précédentes ont soit fourni des bornes de correction prouvables nettement plus faibles (par exemple, autour de $2^{-80}$ ), soit traité l'échelle heuristique comme un problème ouvert nécessitant une justification rigoureuse. Plus précisément, les méthodes rigoureuses existantes traitent souvent la dépendance entre les composantes du ciphertext en remplaçant la distribution jointe réelle par des enveloppes déterministes de pire cas, ce qui entraîne des bornes plus lâches (par exemple, $2^{-127}$ ). Le défi central est de fournir une borne supérieure certifiée qui préserve les dépendances algébriques induites par la matrice publique et les deux termes de compression ( $c_u$ et $c_v$ ) tout en atteignant l'échelle d'échec heuristique.

Méthodologie
Le document opère dans une abstraction explicite ROM/CBD :

Modèle d'Oracle Aléatoire (ROM) : Les flux de génération de la matrice publique séparés par domaine sont modélisés comme des éléments d'anneau uniformes indépendants.
Distribution Binomiale Centrée (CBD) : Les polynômes secrets et de bruit sont modélisés comme des échantillons indépendants avec des coefficients CBD2.
Cartes Entières Exactes : La compression, la décompression et le décodage utilisent les cartes entières exactes auditées de l'ensemble de paramètres ML-KEM-768, et non des approximations en nombres réels.

La stratégie de preuve évite de supposer l'indépendance entre les termes d'erreur. Au lieu de cela, elle emploie une approche de transport préservant la dépendance :

Référence Couplée par Graphe : Les auteurs dérivent un primitif bivarié exact pour le résidu conjoint de $c_u$ et $c_v$ induit par la quantité partagée dépendant de la matrice.
Analyse de Fourier : Ils utilisent un lemme de Fourier partiel pour gérer explicitement le passage des bornes spectrales à la distance de variation totale. Cela permet de transporter la distribution de référence « idéale complète » (où les erreurs sont indépendantes) vers la distribution « idéale propre » réelle (où les dépendances existent) sans perdre la structure de dépendance.
Correction Stratifiée : La preuve gère l'écart par rapport au cas idéal complet en stratifiant selon les facteurs CRT inactifs de l'idéal généré par le vecteur éphémère $r$ $r$ .
- Pour $|T|=1$ et $|T|=2$ (un ou deux facteurs inactifs), des énumérateurs duaux exacts et des certificats spectraux rationnels sont utilisés.
- Pour $|T| \ge 3$ , les auteurs emploient une analyse d'anti-concentration à trois facteurs exhaustive utilisant une construction de type Lattice A et l'énumération de Fincke–Pohst pour borner la probabilité de strates rares.
Bornes Spécifiques aux Bits : L'analyse conclut par des régions de sécurité exactes par bit pour la carte de décodage FIPS, suivies d'une borne d'union sur les 256 coefficients de message. Aucune indépendance n'est supposée entre ces coefficients.

Contributions Clés

Borne Supérieure Préservant la Dépendance : Le document fournit une borne supérieure certifiée pour ML-KEM-768 qui conserve les dépendances algébriques entre $c_u$ et $c_v$ , plutôt que de les remplacer par du bruit de l'arrondi indépendant ou des enveloppes de pire cas.
Transport Bivarié Couplé par Graphe : Les auteurs introduisent une méthode pour transporter la référence idéale complète à travers le mélange d'idéaux affines via un transport d'algèbre de groupe bivarié couplé par graphe, résolvant la dépendance conjointe $c_u/c_v$ .
Contrôle Certifié des Strates Rares : La branche $|T| \ge 3$ est clôturée par une relecture d'anti-concentration à trois facteurs exhaustive, fournissant une borne certifiée pour les cas rares où la structure de l'idéal est hautement dégénérée.
Certificat Rationnel Exact : Le résultat final est un certificat rationnel réduit dérivé de comparaisons entières exactes et d'inégalités rationnelles, évitant les approximations en virgule flottante pour la logique de décision.

Résultats
Le document établit la borne supérieure suivante pour la probabilité d'échec de décapsulation honnête ( $K' \neq K$ ) dans l'abstraction ROM/CBD énoncée :
$\Pr[K' \neq K] \le P^* \le 2^{-164,81}$
L'exposant certifié exact est $-\log_2 P^* = 164,810716201343121\dots$ .

Le seuil $164,81$ est exact mais numériquement serré ; l'exposant certifié dépasse celui-ci de seulement $\approx 0,0007162$ bits.
La valeur $2^{-164,82}$ n'est pas certifiée par cette preuve.
Le résultat est une borne supérieure, et non un taux de défaillance de décryptage (DFR) exact.

Signification et Revendications
Les auteurs précisent explicitement ce que le résultat est et n'est pas :

Ce qu'il est : Une borne supérieure certifiée préservant la dépendance au sein de l'abstraction explicite ROM/CBD. Il comble le fossé entre la correction prouvable (qui est souvent plus faible) et les estimations heuristiques en rendant compte rigoureusement des dépendances algébriques que les modèles heuristiques ignoreent souvent.
Ce qu'il N'EST PAS :
- Ce n'est pas un énoncé information-théorique concernant l'instanciation SHAKE fixe de la FIPS 203.
- Ce n'est pas un DFR exact.
- Ce n'est pas une nouvelle réduction IND-CCA ou une preuve de $\delta$ -correction adaptative (où l'adversaire choisit le message après avoir vu les données publiques).
- Il ne revendique pas la priorité pour les outils sous-jacents (idéaux, stratification CRT, anti-concentration de Fourier), qui sont des antécédents établis.

La signification réside dans le fait de fournir la première justification rigoureuse et consciente des dépendances pour l'échelle d'échec heuristique de ML-KEM-768 au sein d'une abstraction bien définie, démontrant que la valeur heuristique n'est pas simplement le résultat d'une hypothèse d'indépendance mais qu'elle tient même lorsque les dépendances sont préservées, à condition que la borne soit légèrement resserrée à $2^{-164,81}$ .

Articles similaires