💻 computer science

What Can Verifiable Decapsulation Tests Certify? Pass Bounds and Fault-Recognition Limits for FO-Based KEMs

Cet article établit des bornes théoriques et des limites de reconnaissance de fautes pour la vérification des mécanismes d'encapsulation de clés basés sur Fujisaki-Okamoto en démontrant que les tests de décapsulation en boîte noire sont fondamentalement contraints par des événements de type « list-hit » localisés et en prouvant que les opérations en dehors du cône de support actif ne peuvent être certifiées en raison de compromis inhérents entre justesse et complétude.

Auteurs originaux : José Luis Delgado Jiménez

Publié 2026-06-04

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : José Luis Delgado Jiménez

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

Imaginez que vous engagiez un serrurier pour construire un coffre-fort de haute sécurité (un Mécanisme d'Encapsulation de Clé, ou KEM). Vous voulez être certain qu'il n'a pas pris de raccourci, comme sauter l'étape où il vérifie son travail avant de vous remettre la clé.

Dans le monde de la cryptographie post-quantique, il existe une méthode standard pour vérifier ce travail appelée la transformation de Fujisaki–Okamoto (FO). C'est comme une vérification par « re-chiffrement » : le serrurier déchiffre un message, le re-chiffre, puis compare le résultat avec l'original. Si les deux correspondent, la clé est bonne. Si le serrurier saute cette vérification, il pourrait vous donner la bonne clé par accident, ou bien une mauvaise clé.

Ce document présente une nouvelle façon, extrêmement stricte, de tester ces serruriers en utilisant la Décapsulation Vérifiable. Voici le détail de ce que les auteurs ont découvert, en utilisant des analogies simples.

1. Le tour du « Témoin Caché »

Les auteurs proposent une modification où la clé finale ne dépend pas seulement du message, mais aussi d'un « témoin » caché (un code secret généré lors de la re-vérification).

L'analogie : Imaginez que le serrurier doive écrire un code secret sur un morceau de papier après avoir terminé son travail, mais avant de vous donner la clé. Ce code est ensuite verrouillé à l'intérieur de la clé elle-même.
Le test : Vous (le testeur) donnez au serrurier une boîte verrouillée. Il doit l'ouvrir, faire son travail, générer ce code secret, et vous rendre la clé.
Le piège : Vous ne lui dites pas quel devrait être le code secret. Vous ne le saurez que plus tard. Si le serrurier a sauté la re-vérification, il ne connaîtra pas le code secret. S'il devine le mauvais code, la clé qu'il vous donnera sera incorrecte.

2. Le problème de la « Boîte Noire »

Le document pose la question suivante : Pouvons-nous prouver que le serrurier a réellement fait le travail simplement en regardant la clé qu'il nous a donnée ?

Les auteurs disent oui, mais avec des limites. Ils ont découvert que le test ne peut certifier que le serrurier a fait le travail si le code secret était véritablement imprévisible.

La limite de la « Liste de Coups » : Imaginez que le serrurier soit un tricheur qui tente de deviner le code secret. S'il possède une liste de 100 codes possibles, il a une chance sur 100 de réussir par chance. Le document prouve que la probabilité que le serrurier réussisse le test est directement liée à la taille de sa « liste de devinettes ».
La conclusion : Si le serrurier réussit le test, c'est soit parce qu'il a fait le travail correctement, soit parce qu'il a eu une chance incroyable en devinant. Le test ne peut pas faire la différence entre un « travail acharné » et une « chance insolente » à moins de pouvoir prouver que la devinette était impossible.

3. Le « Cône de Dépendance » (Ce que vous ne pouvez pas voir)

C'est la partie la plus profonde du document. Les auteurs définissent un « Cône de Dépendance ».

L'analogie : Considérez le travail du serrurier comme un arbre. Le « code secret » est le fruit tout en haut. Le « Cône de Dépendance » est l'ensemble spécifique de branches et de feuilles qui doivent être touchées pour faire pousser ce fruit.
La découverte : Si le serrurier saute une étape qui se trouve en dehors de ce cône (comme polir une feuille qui n'affecte pas le fruit), aucun test de boîte noire ne pourra prouver qu'il l'a sautée.
Pourquoi ? Parce que vous pouvez construire un « faux » serrurier qui saute cette étape spécifique mais produit exactement le même fruit (la clé) et la même trace écrite. Pour un observateur extérieur, le faux serrurier est identique au vrai.
La règle : Vous ne pouvez certifier que le serrurier a fait le travail si l'étape sautée se trouvait à l'intérieur du cône menant au code secret. Si elle est à l'extérieur, le test est aveugle à cela.

4. Deux façons de réussir le test

Le document montre deux façons pour un serrurier de prouver qu'il a fait le travail :

La voie de la « Sécurité de la Source » : Si le code secret est généré d'une manière mathématiquement prouvée comme étant impossible à deviner (comme un générateur de nombres aléatoires parfait), alors réussir le test prouve que le travail a été fait.
La voie de l'« Entropie » : Si le code secret est suffisamment long et complexe (haute entropie), la probabilité de le deviner est si infime qu'elle est pratiquement nulle. Le document calcule exactement la longueur et la complexité nécessaires pour que le test soit fiable.

5. Tests en conditions réelles (ML-KEM et HQC)

Les auteurs ont testé cette théorie sur deux standards cryptographiques du monde réel : ML-KEM (utilisé dans FIPS 203) et HQC.

L'expérience : Ils ont créé des versions « mutantes » du code qui sautent intentionnellement des étapes (comme sauter la re-vérification ou ignorer une partie de la comparaison).
Les résultats :
- Fautes de Liaison (Binding Faults) : Lorsque le mutant a sauté la partie qui génère le code secret, le test l'a attrapé 100 % du temps.
- Fautes de Décision (Decision Faults) : Lorsque le mutant a sauté une étape qui n'importait que pour de mauvaises entrées (comme une boîte malformée), le test ne l'a pas attrapé sur les bonnes entrées. Cela prouve que le test n'est aussi bon que les entrées que vous lui donnez.
- Fautes Symétriques (Symmetric Faults) : Si le mutant a sauté l'étape des deux côtés, côté expéditeur et côté destinataire, le test n'a pas réussi à le démasquer lorsqu'il se testait lui-même (car ils étaient d'accord entre eux). Mais lorsqu'il a été testé contre une référence « honnête », le test l'a attrapé.

6. Le piège de l'« Auto-test »

Une découverte majeure est que se tester soi-même ne suffit pas.

L'analogie : Si un étudiant rédige un examen puis corrige sa propre copie, il pourrait s'attribuer une note de passage même s'il a triché, car il sait à quoi les réponses devraient ressembler.
Le verdict du document : Pour véritablement vérifier le travail, vous avez besoin d'un test de « Référence Honnête ». Vous avez besoin d'une partie indépendante et fiable (le « harnais ») pour vérifier le travail par rapport à une vérité cachée. Si le système ne fait que se vérifier lui-même, il peut dissimuler de nombreux types de tricherie.

Résumé des affirmations

Ce que le test certifie : Il certifie que le système a calculé une valeur de « témoin secret » spécifique.
Ce que le test ne peut pas certifier : Il ne peut pas certifier que le système a effectué chaque étape de l'algorithme, seulement les étapes qui influencent directement ce témoin secret.
La règle du « Cône » : Si une étape est en dehors du « cône » d'influence menant au témoin secret, un test de boîte noire ne peut pas prouver qu'elle a été effectuée.
La règle de la « Devinette » : Le test n'est aussi fort que la difficulté de deviner le témoin secret. Si le témoin est court, le système peut réussir en devinant.

En résumé, ce document fournit un manuel mathématique pour construire un « détecteur de mensonges » pour le code cryptographique. Il indique précisément ce que ce détecteur de mensonges peut voir, ce qu'il ne peut pas voir, et comment rendre le « code secret » assez difficile à deviner pour que le détecteur devienne fiable.

Résumé technique : Tests de décapsulation vérifiables pour les KEM basés sur FO

Énoncé du problème

Les mécanismes d'encapsulation de clé (KEM) post-quantiques basés sur la transformation de Fujisaki–Okamoto (FO) reposent sur une vérification de décapsulation critique : l'algorithme doit décrypter un texte chiffré, redériver l'aléa de chiffrement, re-calculer le texte chiffré et le comparer à celui reçu avant de dériver le secret partagé. Bien que cette vérification soit critique pour la sécurité, les tests standards d'entrée-sortie en boîte noire échouent souvent à détecter des fautes d'implémentation spécifiques. Une implémentation pourrait omettre certaines parties du calcul de re-chiffrement ou altérer la logique de sélection de branche tout en retournant toujours le secret partagé attendu sur des textes chiffrés honnêtes, contournant ainsi la vérification de sécurité sans déclencher d'échec dans un banc de test standard.

Le document traite de ce qui peut être formellement certifié concernant l'exécution de ces vérifications de décapsulation à l'aide de tests en boîte noire, spécifiquement lorsque le KEM est augmenté de codes de confirmation.

Méthodologie et modèle

Les auteurs proposent une théorie formelle de la décapsulation FO augmentée par code de confirmation testée sous un harnais de référence honnête.

La construction augmentée

Le modèle étend les KEM standards basés sur FO en introduisant un témoin de confirmation caché $W$ dans la dérivation de la clé finale.

Encapsulation : Génère un texte chiffré et une valeur de confirmation interne $W$ . La clé finale $K$ est dérivée comme $K = G_K(\langle \text{good}, B, W \rangle)$ , où $B$ est un préfixe de transcript localisé et $G_K$ est un oracle aléatoire.
Décapsulation : Re-calcule le texte chiffré et le témoin de confirmation $W'$ . La clé finale est dérivée uniquement si $W' = W$ .
Harnais de référence honnête : Le banc de test fournit l'entrée de décapsulation (texte chiffré, clés) mais retient le témoin caché $W$ et la clé finale $K$ . Le Système Sous Test (SUT) doit interroger l'oracle aléatoire $G_K$ avec le tuple correct $\langle \text{good}, B, W \rangle$ pour produire la clé correcte.

Cadre théorique

Le document définit une liste de requêtes de clé finale localisée $Q_G(B)$ , représentant l'ensemble des témoins candidats que le SUT interroge contre l'oracle aléatoire. Le cœur de la méthodologie consiste à borner la probabilité qu'un SUT défectueux réussisse le test (c'est-à-dire qu'il retourne la clé correcte) en analysant la probabilité d'un « coup de liste » (list hit) — l'événement où le témoin caché $W$ se trouve dans $Q_G(B)$ .

L'analyse distingue :

Test de référence honnête : Comparaison du SUT par rapport à un pair sain généré par la référence.
Test de soi honnête : Comparaison du SUT par rapport à lui-même (l'encapsulation et la décapsulation provenant toutes deux du SUT).
Cônes de dépendance : Identification de l'ensemble des opérations qui influencent réellement le vecteur cible observable (le transcript et la clé finale).

Principales contributions

1. Théorème de détectabilité de coup de liste serré

Le résultat central (Théorème 5.1) établit que pour tout SUT $q$ -localisé, la probabilité de réussite sous un harnais de référence honnête est bornée par :
$\text{Pass} \leq \delta_{\Pi_C} + \epsilon_{\text{alias}} + \epsilon_{\text{fresh}} + \Pr[W \in Q_G(B)] + 2^{-\kappa}$
Où :

$\delta_{\Pi_C}$ est l'erreur de correction honnête.
$\epsilon_{\text{alias}}$ rend compte de l'aliasing adversaire (collisions dans l'encodage de la clé finale).
$\epsilon_{\text{fresh}}$ rend compte des défauts de fraîcheur de la clé finale (fuite du point caché).
$\Pr[W \in Q_G(B)]$ est le terme de coup de liste, représentant la probabilité que le SUT devine le témoin caché.
$2^{-\kappa}$ est le terme de coïncidence de l'oracle aléatoire.

Le document prouve que cette borne est serrée (Théorème 5.2) : tout prédicteur de $W$ à partir de la vue du SUT induit un SUT à une requête dont la probabilité de réussite correspond au taux de succès du prédicteur. Ainsi, le terme de coup de liste est l'obstacle fondamental mesuré par le harnais.

2. Deux voies pour borner le terme de coup de liste

Le document propose deux méthodes distinctes pour borner le terme de coup de liste inévitable :

Voie de la sécurité de la source (cUP-fidèle) : Si le harnais est « cUP-fidèle » (fidèle au jeu de non-prédictibilité du code de confirmation de la source), la probabilité de coup de liste est bornée par $q \cdot \epsilon_{\text{cUP}}$ , où $\epsilon_{\text{cUP}}$ est l'avantage d'un adversaire à candidat unique dans le jeu de la source. Cela transfère les preuves de sécurité de la source au contexte de test avec une perte linéaire dans le nombre de requêtes.
Voie entropique : Si le témoin $W$ possède une entropie minimale conditionnelle moyenne $\lambda$ étant donné la vue du SUT, la probabilité de coup de liste est bornée par $q \cdot 2^{-\lambda}$ . Cette voie s'adapte aux codes de diagnostic (par exemple, des hachages tronqués) où les bornes cUP de la source peuvent ne pas s'appliquer directement.

3. Borne inférieure du cône de dépendance (Résultat négatif)

Le document prouve une limitation fondamentale de la certification en boîte noire (Théorème 5.37). Si une opération se situe en dehors du cône de dépendance actif du support de la cible observable (c'est-à-dire que modifier cette opération ne change pas le transcript observable ou la clé finale sur un support honnête), alors pour une classe d'implémentation contenant l'« effacement » correspondant (une version du code qui saute l'opération), les erreurs de validité ( $\alpha$ ) et de complétude ( $\beta$ ) de tout certificateur satisfont $\alpha + \beta \geq 1$ .

Pour de telles opérations, le test en boîte noire ne peut pas distinguer l'exécution correcte de l'effacement des opérations sans instrumentation supplémentaire, d'entrées malformées ou d'un ensemble cible plus large.

4. Instanciations et artefacts

La théorie est instanciée sur deux familles :

ML-KEM (FIPS 203) : Analyse la ligne de code de confirmation de la source (utilisant des coefficients non compressés sélectionnés) et une variante d'artefact de diagnostic (ML-KEM-CD1) utilisant un code haché d'un octet.
HQC (Spécification d'août 2025) : Analyse les variantes FO salées où le code de confirmation est dérivé de la queue de troncature du texte chiffré. Le document définit HQC-TailEnt, une hypothèse requise pour borner le terme de coup de liste pour ces codes dérivés de la queue.

Les auteurs fournissent FO-FaultBench, un artefact reproductible contenant :

Des bases de référence figées (mlkem-native, HQC août 2025).
Des variantes transformées (VSFO/CD1, CD*).
Un catalogue de mutants (fautes de liaison, fautes de décision, fautes symétriques).
Des enregistrements JSONL gelés des exécutions expérimentales.

Résultats expérimentaux

Les campagnes d'artefacts valident les affirmations théoriques :

Fautes de liaison (Binding Faults) : Les fautes qui omettent ou écrasent le code de confirmation sont détectées sous un test de référence honnête, car elles altèrent l'entrée de la clé finale.
Fautes de décision uniquement (Decision-Only Faults) : Les fautes qui n'affectent que la sélection de branche (par exemple, toujours sélectionner la bonne clé) sont non détectées sur des textes chiffrés honnêtes, mais détectées sous des harnais malformés ou différentiels. Cela confirme la limitation de la coïncidence du support.
Fautes symétriques : Les fautes appliquées à la fois à l'encapsulation et à la décapsulation passent les auto-tests mais échouent aux tests de référence honnête, démontant la nécessité du modèle de pair.
Devinette probabiliste : Les mutants qui devinent le code de confirmation réussissent avec une probabilité proportionnelle à la longueur du code conservé ( $2^{-L}$ ), correspondant aux bornes d'entropie théoriques.
Budgets de plage : Les expériences sur les variantes HQC (CD1 vs CD*) montrent que l'augmentation du nombre de bits de queue conservés (de 5 à 37 bits) réduit considérablement la probabilité de réussite des mutants de devinette, validant la voie entropique.

Signification et revendications

Le document prétend fournir une théorie formelle du test de code de confirmation qui délimite précisément ce que les tests en boîte noire peuvent et ne peuvent pas certifier pour les KEM basés sur FO.

Revendications positives : Le document établit que la liaison par code de confirmation crée un signal détectable pour les fautes de re-chiffrement, à condition que le terme de coup de liste soit borné par la cUP de la source ou l'entropie conditionnelle. Il offre un cadre rigoureux pour interpréter les résultats de test comme des preuves de classes de fautes spécifiques.
Revendications négatives : Le document stipule explicitement que le test de référence honnête en boîte noire a des limites inhérentes. Il ne peut pas certifier les opérations situées en dehors du cône de dépendance (par exemple, l'exécution complète du re-chiffrement si seul un sous-ensemble de coefficients est lié) sans changer la cible du harnais ou ajouter de l'instrumentation.
Modestie : Les auteurs soulignent que les théorèmes de test sont des énoncés classiques du Modèle de l'Oracle Aléatoire (ROM). Ils ne reprosent pas la sécurité IND-CCA des KEM sous-jacents mais s'appuient sur les analyses de source citées pour la sécurité de la construction. La « sécurité » des lignes augmentées est héritée de la source ; la contribution du document est le signal de test et l'interprétation des probabilités de réussite sous des configurations de harnais spécifiques.

Ce travail sert de pont entre les jeux de sécurité théoriques (cUP, fCOR) et les tests d'implémentation pratiques, fournissant une « grammaire de revendication » pour interpréter les résultats expérimentaux sur les implémentations de KEM post-quantiques.