pith. sign in

arxiv: 2606.04443 · v1 · pith:JADIQJZTnew · submitted 2026-06-03 · 💻 cs.CR

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

Jos\'e Luis Delgado Jim\'enez This is my paper

Pith reviewed 2026-06-28 06:05 UTC · model grok-4.3

classification 💻 cs.CR
keywords Fujisaki-OkamotoKEMdecapsulationblack-box testsoundnesscompletenessdependency coneerasure implementation
0
0 comments X

The pith

Black-box decapsulation tests for FO KEMs admit coupled erasures outside support-active cones, implying soundness and completeness errors sum to at least 1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper investigates the certification power of black-box verifiable decapsulation tests for Fujisaki-Okamoto based key encapsulation mechanisms under an honest-reference harness fixing a hidden final-key point. It derives acceptance bounds for q-localized systems that incorporate correctness error, aliasing, freshness defects, localized suffix list hits, and a 2 to the minus kappa term. The central result shows that when observations factor through the confirmation-observable final-key target, every operation outside the support-active cone admits a coupled erasure implementation preserving transcript distribution. Over any implementation class containing such an erasure, every execution certifier must satisfy a soundness-completeness error sum of at least 1. The list-hit event is identified as the measurable black-box obstruction and is bounded via cUP certificates or conditional min-entropy.

Core claim

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 α+β≥1. 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.

What carries the argument

The confirmation-observable final-key target through which harness observations factor, enabling the construction of coupled erasure implementations for operations outside the support-active cone.

If this is right

  • Acceptance for a q-localized system is bounded by honest correctness error, adversarial aliasing, final-key freshness defects, a hit on the localized suffix list, and 2 to the minus kappa.
  • A one-query construction from any predictor of the confirmation witness matches the acceptance bound up to the fresh-key coincidence term.
  • The list-hit obstruction is bounded by cUP-faithful certificates with q-loss or by separate RawEnt and TailEnt hypotheses for short and truncation-tail codes.
  • The same model yields a dependency-cone lower bound for non-certification claims.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Effective black-box testing must therefore be restricted to the support-active cone to escape the erasure equivalence.
  • The factoring argument may extend to other verifiable computations whose observations are limited to a designated output target.
  • Relaxing the q-localized premise could permit stronger certification statements in broader implementation classes.

Load-bearing premise

The analysis assumes an honest-reference harness in which the reference encapsulation fixes a hidden final-key point with confirmation witness and that the system under test is q-localized.

What would settle it

Constructing an implementation class containing a transcript-preserving erasure for some operation outside the support-active cone together with an execution certifier achieving soundness error α and completeness error β where α + β is strictly less than 1 would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.04443 by Jos\'e Luis Delgado Jim\'enez.

Figure 1
Figure 1. Figure 1: Simplified split presentation used in the paper. The final good key is evaluated at a canonical [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: August 2025 HQC range-budget sweep under 𝐷honest_ref. The observed points use the full artifact sweep; selected rows are listed in [PITH_FULL_IMAGE:figures/full_fig_p036_2.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper analyzes black-box verifiable decapsulation tests for Fujisaki-Okamoto KEMs under an honest-reference harness fixing a hidden final-key point ⟨good, B, W⟩. For q-localized systems under test, it derives acceptance bounds incorporating honest correctness error, adversarial aliasing, final-key freshness defects, hits on the localized suffix list Q_G(B), and 2^{-κ}. The list-hit term is bounded via cUP-faithful certificates (with q-loss) or average conditional min-entropy (RawEnt/TailEnt hypotheses). It proves a dependency-cone lower bound implying that, when black-box observations factor through the confirmation-observable final-key target, any execution certifier over implementation classes containing the coupled erasure implementation satisfies α + β ≥ 1. ML-KEM and HQC case studies classify rows as theorem-covered, finite-catalog artifacts, or non-certification (with cone-inactivity certificates).

Significance. If the central α + β ≥ 1 result holds, the work establishes a concrete impossibility result for simultaneous low soundness and completeness error in execution certifiers under the stated model, using standard indistinguishability and simulation arguments. This supplies a theoretical limit on fault-recognition power of black-box tests for FO-based KEMs and clarifies the certification status of standard constructions via the case-study distinctions. The explicit conditioning on the honest-support harness and q-localization avoids hidden assumptions.

minor comments (3)
  1. [Abstract] Abstract, paragraph on acceptance bounds: the phrase 'a one-query construction from any predictor of W matches this bound up to the fresh-key coincidence term' would benefit from an explicit statement of the construction (even if deferred to a later section) to make the matching claim self-contained.
  2. [Case studies] The distinction between 'theorem-covered positive rows', 'finite-catalog artifact rows', and 'non-certification rows' in the ML-KEM/HQC case studies is useful but would be clearer if the criteria for each category were listed in a short table or enumerated list.
  3. [Abstract] Notation: the symbol Q_G(B) for the localized suffix list is introduced without an immediate forward reference to its definition; adding the defining equation number in the first use would reduce reader effort.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful and accurate summary of the manuscript, for recognizing the significance of the α + β ≥ 1 lower bound under the honest-support harness, and for the recommendation of minor revision. No major comments requiring point-by-point rebuttal were raised.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation of the central α+β≥1 bound proceeds from the honest-support harness model (with fixed ⟨good,B,W⟩) and the explicit construction of a coupled erasure implementation that preserves transcript distribution when observations factor through the final-key target; this uses standard simulation and indistinguishability arguments without reducing the result to a fitted parameter or self-defined quantity. The list-hit bounds are obtained either via cUP-faithful certificates (transferring unpredictability from cited source analyses with q-loss) or via stated RawEnt/TailEnt hypotheses on conditional min-entropy; both are presented as external modeling inputs rather than quantities defined inside the paper. The one-query construction is shown to match the bound up to a coincidence term, not derived from it. Security of ML-KEM/HQC lines is explicitly delegated to cited source analyses. No step equates a claimed prediction to its inputs by construction, and the paper is self-contained against the stated modeling assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities can be extracted with certainty.

pith-pipeline@v0.9.1-grok · 5864 in / 1266 out tokens · 27032 ms · 2026-06-28T06:05:21.172344+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 13 canonical work pages

  1. [1]

    NIST Special Publication NIST SP 800-227

    Gorjan Alagic et al.Recommendations for Key-Encapsulation Mechanisms. NIST Special Publication NIST SP 800-227. National Institute of Standards and Technology, Sept. 2025.doi: 10.6028/NIST. SP.800-227.url:https://csrc.nist.gov/pubs/sp/800/227/final

    work page doi:10.6028/nist 2025

  2. [2]

    Cryptology ePrint Archive, Paper 2023/755

    Manuel Barbosa and Andreas H"ulsing.The security of Kyber’s FO-transform. Cryptology ePrint Archive, Paper 2023/755. 2023.url:https://eprint.iacr.org/2023/755

    2023

  3. [3]

    Tighter Proofs of CCA Security in the Quantum Random Oracle Model

    Nina Bindel et al. “Tighter Proofs of CCA Security in the Quantum Random Oracle Model”. In: Theory of Cryptography – 17th International Conference, TCC 2019, Nuremberg, Germany, December 1–5, 2019, Proceedings, Part II. Ed. by Dennis Hofheinz and Alon Rosen. Vol. 11892. Lecture Notes in Computer Science. Springer, 2019, pp. 61–90.doi: 10.1007/978-3-030-36...

    work page doi:10.1007/978-3-030-36033-7_3 2019

  4. [4]

    An Injectivity Analysis of Crystals-Kyber and Implications on Quantum Secu- rity

    Xiaohui Ding et al. “An Injectivity Analysis of Crystals-Kyber and Implications on Quantum Secu- rity”. In:Information Security and Privacy – 27th Australasian Conference, ACISP 2022, Wollongong, NSW, Australia, November 28–30, 2022, Proceedings. Ed. by Khoa Nguyen et al. Vol. 13494. Lecture Notes in Computer Science. Springer, 2022, pp. 332–351.doi: 10.1...

    work page doi:10.1007/978-3-031-22301-3_17 2022

  5. [6]

    Faster Lattice-Based KEMs via a Generic Fujisaki-Okamoto Transform Using Prefix Hashing

    Julien Duman et al. “Faster Lattice-Based KEMs via a Generic Fujisaki-Okamoto Transform Using Prefix Hashing”. In:Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 2021, pp. 2722–2737.doi: 10.1145/3460120.3484819.url:https://doi.org/10.1145/3460120.3484819

    work page doi:10.1145/3460120.3484819.url:https://doi.org/10.1145/3460120.3484819 2021

  6. [7]

    Do users write more insecure code with ai assistants?

    Marc Fischlin and Felix G"unther. “Verifiable Verification in Cryptographic Protocols”. In:Proceed- ings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 2023, pp. 3239–3253.doi: 10.1145/3576915.3623151.url: https: //doi.org/10.1145/3576915.3623151

    work page doi:10.1145/3576915.3623151.url: 2023

  7. [8]

    HQC specifications

    Philippe Gaborit et al.Hamming Quasi-Cyclic (HQC). HQC specifications. Aug. 2025.url: https: //pqc-hqc.org/doc/hqc_specifications_2025_08_22.pdf

    2025

  8. [9]

    Measure-Rewind-Extract: Tighter Proofs of One-Way to Hiding and CCA Security in the Quantum Random Oracle Model

    Jiangxia Ge, Heming Liao, and Rui Xue. “Measure-Rewind-Extract: Tighter Proofs of One-Way to Hiding and CCA Security in the Quantum Random Oracle Model”. In:Advances in Cryptology – ASIACRYPT 2024 – 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part IV....

    work page doi:10.1007/978-981-96-0894-2_1.url:https://doi.org/10.1007/978-981-96-0894-2_1 2024

  9. [10]

    Cryptology ePrint Archive, Paper 2023/792

    Jiangxia Ge, Tianshu Shan, and Rui Xue.On the Fujisaki-Okamoto transform: from Classical CCA Security to Quantum CCA Security. Cryptology ePrint Archive, Paper 2023/792. 2023.url: https://eprint.iacr.org/2023/792. 39

    2023

  10. [12]

    Cryptology ePrint Archive, Paper 2025/343

    Lewis Glabush, Kathrin H"ovelmanns, and Douglas Stebila.Tight Multi-challenge Security Reduc- tions for Key Encapsulation Mechanisms. Cryptology ePrint Archive, Paper 2025/343. 2025.url: https://eprint.iacr.org/2025/343

    2025

  11. [13]

    Verifiable Decapsulation: Recognizing Faulty Implementations of Post- quantum KEMs

    Lewis Glabush et al. “Verifiable Decapsulation: Recognizing Faulty Implementations of Post- quantum KEMs”. In:Advances in Cryptology – CRYPTO 2025 – 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part III. Ed. by Yael Tauman Kalai and Seny F. Kamara. Vol. 16002. Lecture Notes in Computer Science. ...

    work page doi:10.1007/978-3-032-01881-6_17 2025

  12. [15]

    ovelmanns and Mikhail A. Kudinov. “Treating Dishonest Ciphertexts in Post-quantum KEMs – Explicit vs. Implicit Rejection in the FO Transform

    Kathrin H"ovelmanns and Mikhail A. Kudinov. “Treating Dishonest Ciphertexts in Post-quantum KEMs – Explicit vs. Implicit Rejection in the FO Transform”. In:Post-Quantum Cryptography – 16th International Workshop, PQCrypto 2025, Taipei, Taiwan, April 8–10, 2025, Proceedings, Part II. Ed. by Ruben Niederhagen and Markku-Juhani O. Saarinen. Vol. 15578. Lectu...

    work page doi:10.1007/978-3-031-86602-9_12 2025

  13. [18]

    In: Královic, R., Kurková, V

    Dennis Hofheinz, Kathrin H"ovelmanns, and Eike Kiltz. “A Modular Analysis of the Fujisaki- Okamoto Transformation”. In:Theory of Cryptography – 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12–15, 2017, Proceedings, Part I. Ed. by Yael Kalai and Leonid Reyzin. Vol. 10677. Lecture Notes in Computer Science. Springer, 2017, pp. 341–3...

    work page doi:10.1007/978- 2017

  14. [19]

    Key Encapsulation Mechanism with Explicit Rejection in the Quantum Random Oracle Model

    Haodong Jiang, Zhenfeng Zhang, and Zhi Ma. “Key Encapsulation Mechanism with Explicit Rejection in the Quantum Random Oracle Model”. In:Public-Key Cryptography – PKC 2019 – 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14–17, 2019, Proceedings, Part II. Ed. by Dongdai Lin and Kazue Sako. Vol. 1...

    work page doi:10.1007/978-3-030-17259-6_21 2019

  15. [20]

    Provable Security Against Decryption Failure Attacks from LWE

    Christian Majenz and Fabrizio Sisinni. “Provable Security Against Decryption Failure Attacks from LWE”. In:Advances in Cryptology – CRYPTO 2024 – 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2024, Proceedings, Part II. Ed. by Leonid Reyzin and Douglas Stebila. Vol. 14921. Lecture Notes in Computer Science. Springe...

    work page doi:10.1007/978-3-031-68379-4_14 2024

  16. [21]

    Federal Information Processing Standards Publication NIST FIPS 203

    National Institute of Standards and Technology.Module-Lattice-Based Key-Encapsulation Mecha- nism Standard. Federal Information Processing Standards Publication NIST FIPS 203. National Institute of Standards and Technology, Aug. 2024.doi: 10.6028/NIST.FIPS.203.url: https: //csrc.nist.gov/pubs/fips/203/final

    work page doi:10.6028/nist.fips.203.url: 2024

  17. [22]

    QCCA-Secure Generic Transformations in the Quantum Random Oracle Model

    Tianshu Shan, Jiangxia Ge, and Rui Xue. “QCCA-Secure Generic Transformations in the Quantum Random Oracle Model”. In:Public-Key Cryptography – PKC 2023 – 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7–10, 2023, Proceedings, Part I. Ed. by Alexandra Boldyreva and Vladimir Kolesnikov. Vol. 13940...

    work page doi:10.1007/978-3-031-31368-4_2 2023