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

Computer Science > Cryptography and Security [Submitted on 3 Jun 2026] What Can Verifiable Decapsulation Tests Certify? Pass Bounds and Fault-Recognition Limits for FO-Based KEMs José Luis Delgado Jiménez Black-box tests for Fujisaki-Okamoto decapsulation observe the sampled execution seen by the harness, whereas the reencryption computation itself is visible only through the values that reach final key derivation. We study confirmation-code-augmented KEM variants under an honest-reference harness in which the reference encapsulation fixes a hidden final-key point \langle good,B,W\rangle, with W the confirmation witness. For a q-localized system under test, acceptance is bounded by honest correctness error, adversarial aliasing, final-key freshness defects, a hit on the localized suffix list Q_G(B), and 2^{-\kappa}. A one-query construction from any predictor of W matches this bound up to the fresh-key coincidence term, so the list-hit event is the black-box obstruction measured by the harness. The list-hit term is bounded either by a cUP-faithful harness certificate, which transfers source confirmation-code unpredictability with a q-loss, or by an average conditional min-entropy bound, with separate RawEnt and TailEnt hypotheses for short diagnostic and truncation-tail codes. The same model proves a dependency-cone lower bound for non-certification claims. When the black-box observation of an honest-support harness factors through the confirmation-observable final-key target, every operation outside the support-active cone has a coupled erasure implementation with the same transcript distribution; over any implementation class containing that erasure, soundness and completeness errors of an execution certifier satisfy \alpha+\beta\ge 1. The ML-KEM and HQC case studies distinguish theorem-covered positive rows, finite-catalog artifact rows, and non-certification rows that carry a cone-inactivity certificate. The security of the standard KEM lines is the construction-level security supplied by the cited source analyses. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2606.04443 [cs.CR]   (or arXiv:2606.04443v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.04443 Focus to learn more Submission history From: José Luis Delgado [view email] [v1] Wed, 3 Jun 2026 04:46:17 UTC (46 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)