💻 computer science

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

This paper establishes theoretical bounds and fault-recognition limits for verifying Fujisaki-Okamoto-based Key Encapsulation Mechanisms by demonstrating that black-box decapsulation tests are fundamentally constrained by localized list-hit events and proving that operations outside the support-active cone cannot be certified due to inherent soundness-completeness trade-offs.

Original authors: José Luis Delgado Jiménez

Published 2026-06-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: José Luis Delgado Jiménez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are hiring a locksmith to build a high-security vault (a Key Encapsulation Mechanism, or KEM). You want to be sure they didn't take a shortcut, like skipping the step where they double-check their work before handing you the key.

In the world of post-quantum cryptography, there's a standard way to check this work called the Fujisaki–Okamoto (FO) transform. It's like a "re-encryption" check: the locksmith decrypts a message, re-encrypts it, and compares the result to the original. If they match, the key is good. If the locksmith skips this check, they might still give you the right key by accident, or they might give you a wrong one.

This paper introduces a new, super-strict way to test these locksmiths using Verifiable Decapsulation. Here is the breakdown of what the authors discovered, using simple analogies.

1. The "Hidden Witness" Trick

The authors propose a modification where the final key isn't just based on the message, but also on a hidden "witness" (a secret code generated during the re-check).

The Analogy: Imagine the locksmith has to write a secret code on a piece of paper after they finish their work, but before they give you the key. This code is then locked inside the key itself.
The Test: You (the tester) give the locksmith a locked box. They must open it, do their work, generate that secret code, and give you back the key.
The Catch: You don't tell them what the secret code should be. You only know it later. If the locksmith skipped the re-check, they won't know the secret code. If they guess the wrong code, the key they give you will be wrong.

2. The "Black Box" Problem

The paper asks: Can we prove the locksmith actually did the work just by looking at the key they gave us?

The authors say yes, but with limits. They found that the test can only certify that the locksmith did the work if the secret code was truly unpredictable.

The "List-Hit" Limit: Imagine the locksmith is a cheat who tries to guess the secret code. If they have a list of 100 possible codes, they have a 1-in-100 chance of getting it right by luck. The paper proves that the probability of the locksmith passing the test is directly tied to the size of their "guessing list."
The Conclusion: If the locksmith passes the test, it's either because they did the work correctly, or they got incredibly lucky with a guess. The test cannot tell the difference between "hard work" and "lucky guessing" unless we can prove the guess was impossible.

3. The "Dependency Cone" (What You Can't See)

This is the most profound part of the paper. The authors define a "Dependency Cone."

The Analogy: Think of the locksmith's work as a tree. The "secret code" is the fruit at the very top. The "Dependency Cone" is the specific set of branches and leaves that must be touched to grow that fruit.
The Discovery: If the locksmith skips a step that is outside this cone (like polishing a leaf that doesn't affect the fruit), no black-box test can prove they skipped it.
Why? Because you can build a "fake" locksmith who skips that specific step but produces the exact same fruit (key) and the exact same paper trail. To the outside observer, the fake locksmith looks identical to the real one.
The Rule: You can only certify that the locksmith did the work if the skipped step was inside the cone that leads to the secret code. If it's outside, the test is blind to it.

4. Two Ways to Pass the Test

The paper shows two ways a locksmith can be proven to have done the work:

The "Source Security" Route: If the secret code is generated in a way that is mathematically proven to be unguessable (like a perfect random number generator), then passing the test proves the work was done.
The "Entropy" Route: If the secret code is long enough and messy enough (high "entropy"), the chance of guessing it is so tiny that it's practically zero. The paper calculates exactly how long and messy the code needs to be to make the test reliable.

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

The authors tested this theory on two real-world cryptographic standards: ML-KEM (used in FIPS 203) and HQC.

The Experiment: They created "mutant" versions of the code that intentionally skipped steps (like skipping the re-check or ignoring part of the comparison).
The Results:
- Binding Faults: When the mutant skipped the part that generates the secret code, the test caught them 100% of the time.
- Decision Faults: When the mutant skipped a step that only mattered for bad inputs (like a malformed box), the test didn't catch them on good inputs. This proves the test is only as good as the inputs you give it.
- Symmetric Faults: If the mutant skipped the step on both the sender and receiver sides, the test failed to catch them when they tested themselves (because they agreed with each other). But when tested against a "honest" reference, the test caught them.

6. The "Self-Test" Trap

A major finding is that testing yourself is not enough.

The Analogy: If a student writes an exam and then grades their own paper, they might give themselves a passing grade even if they cheated, because they know what the answers should look like.
The Paper's Verdict: To truly verify the work, you need an Honest-Reference test. You need an independent, trusted party (the "harness") to check the work against a hidden truth. If the system only checks itself, it can hide many types of cheating.

Summary of Claims

What the test certifies: It certifies that the system computed a specific "secret witness" value.
What the test cannot certify: It cannot certify that the system performed every step of the algorithm, only the steps that directly influence that secret witness.
The "Cone" Rule: If a step is outside the "cone" of influence leading to the secret witness, a black-box test cannot prove it was done.
The "Guessing" Rule: The test is only as strong as the difficulty of guessing the secret witness. If the witness is short, the system can pass by guessing.

In short, this paper provides a mathematical rulebook for how to build a "lie detector" for cryptographic code. It tells us exactly what that lie detector can see, what it is blind to, and how to make the "secret code" hard enough to guess that the lie detector becomes reliable.

Technical Summary: Verifiable Decapsulation Tests for FO-Based KEMs

Problem Statement

Post-quantum Key Encapsulation Mechanisms (KEMs) based on the Fujisaki–Okamoto (FO) transform rely on a critical decapsulation check: the algorithm must decrypt a ciphertext, re-derive the encryption randomness, recompute the ciphertext, and compare it to the received one before deriving the shared secret. While this check is security-critical, standard black-box input-output tests often fail to detect specific implementation faults. An implementation might omit parts of the reencryption computation or alter branch selection logic yet still return the expected shared secret on honestly generated ciphertexts, effectively bypassing the security check without triggering a failure in a standard test harness.

The paper addresses the question of what can be formally certified about the execution of these decapsulation checks using black-box testing, specifically when the KEM is augmented with confirmation codes.

Methodology and Model

The authors propose a formal theory of confirmation-code-augmented FO decapsulation tested under an honest-reference harness.

The Augmented Construction

The model extends standard FO-based KEMs by introducing a hidden confirmation witness $W$ into the final key derivation.

Encapsulation: Generates a ciphertext and an internal confirmation value $W$ . The final key $K$ is derived as $K = G_K(\langle \text{good}, B, W \rangle)$ , where $B$ is a localized transcript prefix and $G_K$ is a random oracle.
Decapsulation: Recomputes the ciphertext and the confirmation witness $W'$ . The final key is derived only if $W' = W$ .
Honest-Reference Harness: The test harness provides the decapsulation input (ciphertext, keys) but withholds the hidden witness $W$ and the final key $K$ . The System Under Test (SUT) must query the random oracle $G_K$ with the correct tuple $\langle \text{good}, B, W \rangle$ to produce the correct key.

Theoretical Framework

The paper defines a localized final-key query list $Q_G(B)$ , representing the set of candidate witnesses the SUT queries against the random oracle. The core of the methodology is bounding the probability that a faulty SUT passes the test (i.e., outputs the correct key) by analyzing the probability of a "list hit"—the event that the hidden witness $W$ is in $Q_G(B)$ .

The analysis distinguishes between:

Honest-Reference Testing: Comparing the SUT against a sound, reference-generated peer.
Honest-Self Testing: Comparing the SUT against itself (encapsulation and decapsulation both from the SUT).
Dependency Cones: Identifying the set of operations that actually influence the observable target vector (the transcript and final key).

Key Contributions

1. Tight List-Hit Detectability Theorem

The central result (Theorem 5.1) establishes that for any $q$ -localized SUT, the pass probability under an honest-reference harness is bounded by:
$\text{Pass} \leq \delta_{\Pi_C} + \epsilon_{\text{alias}} + \epsilon_{\text{fresh}} + \Pr[W \in Q_G(B)] + 2^{-\kappa}$
Where:

$\delta_{\Pi_C}$ is the honest correctness error.
$\epsilon_{\text{alias}}$ accounts for adversarial aliasing (collisions in the final-key encoding).
$\epsilon_{\text{fresh}}$ accounts for final-key freshness defects (leakage of the hidden point).
$\Pr[W \in Q_G(B)]$ is the list-hit term, representing the probability the SUT guesses the hidden witness.
$2^{-\kappa}$ is the random-oracle coincidence term.

The paper proves this bound is tight (Theorem 5.2): any predictor of $W$ from the SUT's view induces a one-query SUT with a pass probability matching the predictor's success rate. Thus, the list-hit term is the fundamental obstruction measured by the harness.

2. Two Routes to Bound the List-Hit Term

The paper provides two distinct methods to bound the unavoidable list-hit term:

Source-Security Route (cUP-faithful): If the harness is "cUP-faithful" (faithful to the source confirmation-code unpredictability game), the list-hit probability is bounded by $q \cdot \epsilon_{\text{cUP}}$ , where $\epsilon_{\text{cUP}}$ is the advantage of a single-candidate adversary in the source game. This transfers source security proofs to the testing context with a linear loss in the number of queries.
Entropic Route: If the witness $W$ has average conditional min-entropy $\lambda$ given the SUT's view, the list-hit probability is bounded by $q \cdot 2^{-\lambda}$ . This route accommodates diagnostic codes (e.g., truncated hashes) where source cUP bounds may not apply directly.

3. Dependency-Cone Lower Bound (Negative Result)

The paper proves a fundamental limitation on black-box certification (Theorem 5.37). If an operation lies outside the support-active dependency cone of the confirmation-observable target (i.e., changing that operation does not change the observable transcript or final key on honest support), then no black-box honest-reference test can certify its execution over an implementation class containing the corresponding "erasure" (a version of the code that skips the operation).

For such operations, the soundness ( $\alpha$ ) and completeness ( $\beta$ ) errors of any certifier satisfy $\alpha + \beta \geq 1$ .
This implies that without additional instrumentation, malformed inputs, or a larger target set, black-box tests cannot distinguish between correct execution and erasure of operations outside the cone.

4. Instantiations and Artifact

The theory is instantiated on two families:

ML-KEM (FIPS 203): Analyzes the source confirmation-code line (using selected uncompressed coefficients) and a diagnostic artifact variant (ML-KEM-CD1) using a one-byte hashed code.
HQC (August 2025 Specification): Analyzes salted FO variants where the confirmation code is derived from the truncation tail of the ciphertext. The paper defines HQC-TailEnt, an assumption required to bound the list-hit term for these tail-derived codes.

The authors provide FO-FaultBench, a reproducible artifact containing:

Pinned baselines (mlkem-native, HQC August 2025).
Transformed variants (VSFO/CD1, CD*).
Mutant catalogs (binding faults, decision faults, symmetric faults).
Frozen JSONL records of experimental runs.

Experimental Results

The artifact campaigns validate the theoretical claims:

Binding Faults: Faults that omit or overwrite the confirmation code are detected under honest-reference testing, as they alter the final-key input.
Decision-Only Faults: Faults that only affect branch selection (e.g., always selecting the good key) are undetected on honest ciphertexts but detected under malformed or differential harnesses. This confirms the support-coincidence limitation.
Symmetric Faults: Faults applied to both encapsulation and decapsulation pass self-tests but fail honest-reference tests, demonstrating the necessity of the peer model.
Probabilistic Guessing: Mutants that guess the confirmation code pass with a probability scaling with the retained code length ( $2^{-L}$ ), matching the theoretical entropy bounds.
Range Budgets: Experiments on HQC variants (CD1 vs. CD*) show that increasing the retained tail bits (from 5 to 37 bits) significantly reduces the pass probability of guessing mutants, validating the entropic route.

Significance and Claims

The paper claims to provide a formal theory of confirmation-code testing that precisely delineates what black-box tests can and cannot certify for FO-based KEMs.

Positive Claims: The paper establishes that confirmation-code binding creates a detectable signal for reencryption faults, provided the list-hit term is bounded by source cUP or conditional entropy. It offers a rigorous framework to interpret test results as evidence for specific fault classes.
Negative Claims: The paper explicitly states that black-box honest-reference testing has inherent limits. It cannot certify operations outside the dependency cone (e.g., full reencryption execution if only a subset of coefficients is bound) without changing the harness target or adding instrumentation.
Modesty: The authors emphasize that the testing theorems are classical Random Oracle Model (ROM) statements. They do not reprove the IND-CCA security of the underlying KEMs but rely on cited source analyses for construction-level security. The "security" of the augmented lines is inherited from the source; the paper's contribution is the testing signal and the interpretation of pass probabilities under specific harness configurations.

The work serves as a bridge between theoretical security games (cUP, fCOR) and practical implementation testing, providing a "claim grammar" for interpreting experimental results on post-quantum KEM implementations.