💻 computer science

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

Dit artikel stelt theoretische grenzen en foutherkenningslimieten vast voor het verifiëren van op Fujisaki-Okamoto gebaseerde Key Encapsulation Mechanisms door aan te tonen dat black-box decapsulatie-tests fundamenteel worden beperkt door gelokaliseerde list-hit gebeurtenissen en door te bewijzen dat operaties buiten de support-active cone niet gecertificeerd kunnen worden vanwege inherente soundness-completeness trade-offs.

Oorspronkelijke auteurs: José Luis Delgado Jiménez

Gepubliceerd 2026-06-04

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: José Luis Delgado Jiménez

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een slotenmaker inhuurt om een hoogbeveiligde kluis te bouwen (een Key Encapsulation Mechanism, of KEM). Je wilt er zeker van zijn dat hij geen kortere weg heeft genomen, zoals het overslaan van de stap waarbij hij zijn werk dubbelcheckt voordat hij de sleutel aan je overhandigt.

In de wereld van post-quantum cryptografie is er een standaard manier om dit werk te controleren, genaamd de Fujisaki–Okamoto (FO) transformatie. Dit is als een "re-encryptie" controle: de slotenmaker ontsleutelt een bericht, versleutelt het opnieuw en vergelijkt het resultaat met het origineel. Als ze overeenkomen, is de sleutel goed. Als de slotenmaker deze controle overslaat, kan hij je per ongeluk de juiste sleutel geven, of hij kan je een verkeerde geven.

Dit artikel introduceert een nieuwe, superstrikte manier om deze slotenmakers te testen met behulp van Verifiable Decapsulation. Hier is de uitsplitsing van wat de auteurs hebben ontdekt, gebruikmakend van eenvoudige analogieën.

1. De "Verborgen Getuige" Truc

De auteurs stellen een modificatie voor waarbij de uiteindelijke sleutel niet alleen gebaseerd is op het bericht, maar ook op een verborgen "getuige" (een geheime code die tijdens de controle wordt gegenereerd).

De Analogie: Stel je voor dat de slotenmaker een geheime code op een papiertje moet schrijven nadat hij zijn werk heeft voltooid, maar voordat hij de sleutel aan je geeft. Deze code wordt vervolgens in de sleutel zelf opgesloten.
De Test: Jij (de tester) geeft de slotenmaker een afgesloten doos. Hij moet de doos openen, zijn werk doen, die geheime code genereren en de sleutel aan jou teruggeven.
De Catch: Je vertelt hem niet wat de geheime code zou moeten zijn. Je weet het pas later. Als de slotenmaker de controle heeft overgeslagen, zal hij de geheime code niet weten. Als hij de verkeerde code raadt, zal de sleutel die hij geeft fout zijn.

2. Het "Black Box" Probleem

Het artikel vraagt: Kunnen we bewijzen dat de slotenmaker het werk daadwerkelijk heeft uitgevoerd door alleen naar de sleutel te kijken die hij ons gaf?

De auteurs zeggen ja, maar met beperkingen. Ze ontdekten dat de test alleen kan certificeren dat de slotenmaker het werk heeft gedaan als de geheime code werkelijk onvoorspelbaar was.

De "List-Hit" Limiet: Stel je voor dat de slotenmaker een bedrieger is die probeert de geheime code te raden. Als hij een lijst heeft van 100 mogelijke codes, heeft hij 1 op 100 kans om het door geluk goed te hebben. Het artikel bewijst dat de kans dat de slotenmaker slaagt voor de test direct verbonden is aan de grootte van zijn "goklijst".
De Conclusie: Als de slotenmaker slaagt voor de test, is dat ofwel omdat hij het werk correct heeft uitgevoerd, ofwel omdat hij ongelooflijk veel geluk had met een gok. De test kan het verschil niet zien tussen "hard werken" en "gelukkig gokken", tenzij we kunnen bewijzen dat de gok onmogelijk was.

3. De "Dependency Cone" (Wat je niet kunt zien)

Dit is het meest diepgaande deel van het artikel. De auteurs definiëren een "Dependency Cone" (afhankelijkheids-kegel).

De Analogie: Denk aan het werk van de slotenmaker als een boom. De "geheime code" is de vrucht aan de top van de boom. De "Dependency Cone" is de specifieke set takken en bladeren die moeten worden aangeraakt om die vrucht te laten groeien.
De Ontdekking: Als de slotenmaker een stap overslaat die buiten deze kegel valt (zoals het polijsten van een blad dat geen invloed heeft op de vrucht), kan geen enkele black-box test bewijzen dat hij dit heeft overgeslagen.
Waarom? Omdat je een "nep" slotenmaker kunt bouwen die die specifieke stap overslaat, maar toch exact dezelfde vrucht (sleutel) en exact hetzelfde papierwerk produceert. Voor een externe waarnemer ziet de nep-slotenmaker er identiek uit aan de echte slotenmaker.
De Regel: Je kunt alleen certificeren dat de slotenmaker het werk heeft gedaan als de overgeslagen stap binnen de kegel viel die naar de geheime code leidt. Als het er buiten valt, is de test blind voor dat.

4. Twee manieren om de test te halen

Het artikel laat twee manieren zien waarop een slotenmaker kan bewijzen dat hij het werk heeft gedaan:

De "Source Security" Route: Als de geheime code op een manier wordt gegenereerd die wiskundig bewezen onpeilbaar is (zoals een perfecte willekeurige nummergenerator), dan bewijst het slagen voor de test dat het werk is uitgevoerd.
De "Entropy" Route: Als de geheime code lang genoeg en chaotisch genoeg is (hoge "entropie"), is de kans op het raden ervan zo klein dat het praktisch nul is. Het artikel berekent precies hoe lang en chaotisch de code moet zijn om de test betrouwbaar te maken.

5. Real-World Tests (ML-KEM en HQC)

De auteurs hebben deze theorie getest op twee real-world cryptografische standaarden: ML-KEM (gebruikt in FIPS 203) en HQC.

Het Experiment: Ze creëerden "mutant" versies van de code die opzettelijk stappen oversloegen (zoals het overslaan van de re-encryptie of het negeren van een deel van de vergelijking).
De Resultaten:
- Binding Faults: Wanneer de mutant het deel oversloeg dat de geheime code genereert, betrapt de test hen 100% van de tijd.
- Decision Faults: Wanneer de mutant een stap oversloeg die alleen belangrijk was voor slechte inputs (zoals een defecte doos), betrapte de test hen niet bij goede inputs. Dit bewijst dat de test slechts zo goed is als de inputs die je eraan geeft.
- Symmetric Faults: Als de mutant de stap aan zowel de zender- als de ontvangerzijde oversloeg, faalde de test om hen te betrappen wanneer zij zichzelf testten (omdat ze het met elkaar eens waren). Maar wanneer ze tegen een "eerlijke" referentie werden getest, betrapte de test hen wel.

6. De "Self-Test" Valstrik

Een belangrijke bevinding is dat jezelf testen niet genoeg is.

De Analogie: Als een student een examen schrijft en daarna zijn eigen werk nakijkt, kan hij zichzelf een voldoende geven, zelfs als hij heeft gesjoemeld, omdat hij weet hoe de antwoorden eruit zouden moeten zien.
Het Oordeel van het Artikel: Om het werk echt te verifiëren, heb je een Honest-Reference test nodig. Je hebt een onafhankelijke, vertrouwde partij (de "harness") nodig om het werk te controleren tegen een verborgen waarheid. Als het systeem alleen zichzelf controleert, kan het veel soorten bedrog verbergen.

Samenvatting van de claims

Wat de test certificeert: Het certificeert dat het systeem een specifieke "geheime getuige" waarde heeft berekend.
Wat de test niet kan certificeren: Het kan niet certificeren dat het systeem elke stap van het algoritme heeft uitgevoerd, alleen de stappen die de geheime getuige direct beïnvloeden.
De "Cone" Regel: Als een stap buiten de "kegel" van invloed valt die naar de geheime getuige leidt, kan een black-box test niet bewijzen dat deze is uitgevoerd.
De "Guessing" Regel: De test is slechts zo sterk als de moeilijkheid van het raden van de geheime getuige. Als de getuige kort is, kan het systeem slagen door te gokken.

Kortom, dit artikel biedt een wiskundig regelboek voor hoe je een "leugendetector" voor cryptografische code bouwt. Het vertelt ons precies wat die leugendetector kan zien, waar hij blind voor is, en hoe je de "geheime code" moeilijk genoeg kunt maken om te raden, zodat de leugendetector betrouwbaar wordt.

Technische Samenvatting: Verifieerbare Decapsulatie-testen voor FO-gebaseerde KEM's

Probleemstelling

Post-quantum Key Encapsulation Mechanisms (KEM's) gebaseerd op de Fujisaki–Okamoto (FO) transformatie vertrouwen op een cruciale decapsulatie-controle: het algoritme moet de ciphertext decoderen, de encryptie-randomness opnieuw afleiden, de ciphertext opnieuw berekenen en deze vergelijken met de ontvangen versie voordat de gedeelde sleutel wordt afgeleid. Hoewel deze controle essentieel is voor de veiligheid, falen standaard black-box input-output testen vaak bij het detecteren van specifieke implementatiefouten. Een implementatie kan delen van de herencryptie-berekening weglaten of de logica van de vertakkingsselectie wijzigen, terwijl nog steeds de verwachte gedeelde sleutel teruggeeft op eerlijk gegenereerde ciphertexts, waardoor de veiligheidscontrole effectief wordt omzeild zonder een fout te triggeren in een standaard testframework.

Dit artikel behandelt de vraag wat er formeel gecertificeerd kan worden over de uitvoering van deze decapsulatie-controles met behulp van black-box testen, specifiek wanneer de KEM wordt uitgebreid met bevestigingscodes (confirmation codes).

Methodologie en Model

De auteurs stellen een formele theorie voor van bevestigingscode-geaugmenteerde FO-decapsulatie getest onder een honest-reference harness (eerlijke referentie-harness).

De Geaugmenteerde Constructie

Het model breidt standaard FO-gebaseerde KEM's uit door een verborgen bevestigingsgetuige (confirmation witness) $W$ toe te voegen aan de uiteindelijke sleutelafleiding.

Encapsulatie: Genereert een ciphertext en een interne bevestigingswaarde $W$ . De uiteindelijke sleutel $K$ wordt afgeleid als $K = G_K(\langle \text{good}, B, W \rangle)$ , waarbij $B$ een gelokaliseerde transcript-prefix is en $G_K$ een random oracle is.
Decapsulatie: Herberekent de ciphertext en de bevestigingsgetuige $W'$ . De uiteindelijke sleutel wordt alleen afgeleid als $W' = W$ .
Honest-Reference Harness: De testharness levert de decapsulatie-input (ciphertext, sleutels) maar houdt de verborgen getuige $W$ en de uiteindelijke sleutel $K$ achter. De System Under Test (SUT) moet de random oracle $G_K$ bevragen met de correcte tuple $\langle \text{good}, B, W \rangle$ om de juiste sleutel te produceren.

Theoretisch Kader

Het artikel definieert een gelokaliseerde lijst met finale-sleutel-queries $Q_G(B)$ , die de verzameling potentiële getuigen vertegenwoordigt die de SUT tegen de random oracle bevraagt. De kern van de methodologie is het begrenzen van de waarschijnlijkheid dat een defecte SUT de test slaagt (d.w.z. de correcte sleutel teruggeeft) door de waarschijnlijkheid van een "list hit" te analyseren: het evenement dat de verborgen getuige $W$ in $Q_G(B)$ zit.

De analyse maakt onderscheid tussen:

Honest-Reference Testing: Het vergelijken van de SUT met een betrouwbare, door een referentie gegenereerde peer.
Honest-Self Testing: Het vergelijken van de SUT met zichzelf (zowel encapsulatie als decapsulatie afkomstig van de SUT).
Dependency Cones (Afhankelijkheidsconussen): Het identificeren van de verzameling operaties die daadwerkelijk invloed hebben op de observeerbare doelvector (het transcript en de finale sleutel).

Belangrijkste Bijdragen

1. Nauwe List-Hit Detectabiliteitstelling

De centrale resultaat (Theorem 5.1) stelt dat voor elke $q$ -gelokaliseerde SUT, de slaagkans onder een honest-reference harness wordt begrensd door:
$\text{Pass} \leq \delta_{\Pi_C} + \epsilon_{\text{alias}} + \epsilon_{\text{fresh}} + \Pr[W \in Q_G(B)] + 2^{-\kappa}$
Waar:

$\delta_{\Pi_C}$ de eerlijke correctiefout is.
$\epsilon_{\text{alias}}$ rekening houdt met adversariële aliasing (botsingen in de final-key encoding).
$\epsilon_{\text{fresh}}$ rekening houdt met final-key freshness defecten (lekken van het verborgen punt).
$\Pr[W \in Q_G(B)]$ de list-hit term is, die de waarschijnlijkheid vertegenwoordigt dat de SUT de verborgen getuige raadt.
$2^{-\kappa}$ de random-oracle toevalligheidsterm is.

Het artikel bewijst dat deze grens nauw is (Theorem 5.2): elke voorspeller van $W$ vanuit het perspectief van de SUT induceert een one-query SUT met een slaagkans die overeenkomt met het succespercentage van de voorspeller. Hiermee is de list-hit term de fundamentele obstructie die door de harness wordt gemeten.

2. Twee Routes om de List-Hit Term te Begrenzen

Het artikel biedt twee verschillende methoden om de onvermijdelijke list-hit term te begrenzen:

Source-Security Route (cUP-getrouw): Als de harness "cUP-getrouw" is (getrouw aan het bron-bevestigingscode onvoorspelbaarheidsspel), wordt de list-hit waarschijnlijkheid begrensd door $q \cdot \epsilon_{\text{cUP}}$ , waarbij $\epsilon_{\text{cUP}}$ het voordeel van een single-candidate adversary in het bronspel is. Dit draagt de beveiligingsbewijzen van de bron over naar de testcontext met een lineair verlies in het aantal queries.
Entropische Route: Als de getuige $W$ een gemiddelde conditionele min-entropie $\lambda$ heeft gegeven de view van de SUT, wordt de list-hit waarschijnlijkheid begrensd door $q \cdot 2^{-\lambda}$ . Deze route is geschikt voor diagnostische codes (bijv. getrunceerde hashes) waarbij directe bounds voor de bron-cUP mogelijk niet van toepassing zijn.

3. Dependency-Cone Ondergrens (Negatief Resultaat)

Het artikel bewijst een fundamentele beperking van black-box certificering (Theorem 5.37). Als een operatie buiten de support-active dependency cone van de bevestigings-observeerbare doelwaarde ligt (d.w.z. het veranderen van die operatie verandert de observeerbare transcript of de finale sleutel niet op eerlijke support), dan kan geen enkele black-box honest-reference test de uitvoering ervan certificeren over een implementatieklasse die de overeenkomstige "erasure" bevat (een versie van de code die de operatie overslaat).

Voor dergelijke operaties voldoen de soundness ( $\alpha$ ) en completeness ( $\beta$ ) fouten van elke certifier aan $\alpha + \beta \geq 1$ .
Dit impliceert dat zonder aanvullende instrumentatie, malafide inputs of een grotere doelset, black-box testen niet het verschil kunnen zien tussen correcte uitvoering en het weglaten van operaties buiten de cone.

4. Instantiaties en Artefact

De theorie wordt geïnstantieerd op twee families:

ML-KEM (FIPS 203): Analyseert de bron bevestigingscode-lijn (gebruikmakend van geselecteerde ongecomprimeerde coëfficiënten) en een diagnostische artefact variant (ML-KEM-CD1) met gebruik van een één-byte gehashte code.
HQC (Augustus 2025 Specificatie): Analyseert gezouten FO-varianten waarbij de bevestigingscode wordt afgeleid van de getrunceerde staart van de ciphertext. Het artikel definieert HQC-TailEnt, een assumptie die vereist is om de list-hit term voor deze staart-afgeleide codes te begrenzen.

De auteurs bieden FO-FaultBench, een reproduceerbaar artefact dat bevat:

Vastgelegde baselines (mlkem-native, HQC Augustus 2025).
Getransformeerde varianten (VSFO/CD1, CD*).
Mutant catalogi (binding faults, decision faults, symmetric faults).
Bevroren JSONL-records van experimentele runs.

Experimentele Resultaten

De campagne met het artefact valideert de theoretische claims:

Binding Faults: Fouten die de bevestigingscode weglaten of overschrijven, worden gedetecteerd onder honest-reference testing, omdat ze de input van de finale sleutel wijzigen.
Decision-Only Faults: Fouten die alleen de vertakkingsselectie beïnvloeden (bijv. altijd de goede sleutel selecteren) worden niet gedetecteerd op eerlijke ciphertexts, maar wel onder malafide of differentiële harnesses. Dit bevestigt de support-coincidence beperking.
Symmetric Faults: Fouten toegepast op zowel de encapsulatie als de decapsulatie passen zelf-testen, maar falen bij honest-reference testen, wat de noodzaak van het peer-model aantoont.
Probabilistisch Gokken: Mutanten die de bevestigingscode raden, slagen met een waarschijnlijkheid die schaalt met de behouden code-lengte ( $2^{-L}$ ), wat overeenkomt met de theoretische entropie-bounds.
Range Budgets: Experimenten op HQC-varianten (CD1 vs. CD*) laten zien dat het vergroten van de behouden staartbits (van 5 naar 37 bits) de slaagkans van gok-mutanten aanzienlijk vermindert, wat de entropische route valideert.

Betekenis en Claims

Het artikel claimt een formele theorie van bevestigingscode-testen te bieden die precies omschrijft wat black-box testen wel en niet kunnen certificeren voor FO-gebaseerde KEM's.

Positieve Claims: Het artikel stelt dat bevestigingscode-binding een detecteerbaar signaal creëert voor reencryptie-fouten, mits de list-hit term wordt begrensd door bron-cUP of conditionele entropie. Het biedt een rigoureus kader om testresultaten te interpreteren als bewijs voor specifieke foutklassen.
Negatieve Claims: Het artikel stelt expliciet dat black-box honest-reference testing inherente limieten heeft. Het kan operaties buiten de dependency cone (bijv. volledige uitvoering van herencryptie als slechts een subset van coëfficiënten wordt gebonden) niet certificeren zonder de harness-target te wijzigen of instrumentatie toe te voegen.
Bescheidenheid: De auteurs benadrukken dat de testen klassieke Random Oracle Model (ROM) uitspraken zijn. Ze proberen niet de IND-CCA beveiliging van de onderliggende KEM's opnieuw te bewijzen, maar vertrouwen op geciteerde bronanalyses voor constructie-niveau beveiliging. De "beveiliging" van de uitgebreide lijnen wordt geërfd van de bron; de bijdrage van het artikel is het testsignaal en de interpretatie van slaagkansen onder specifieke harness-configuraties.

Het werk dient als een brug tussen theoretische beveiligingsspellen (cUP, fCOR) en praktische implementatie-testen, en biedt een "claim grammatica" voor het interpreteren van experimentele resultaten op post-quantum KEM-implementaties.