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

• URL: http://arxiv.org/abs/2606.04443v1
• Date: Wed, 03 Jun 2026 04:46:17 GMT
• Title: What Can Verifiable Decapsulation Tests Certify? Pass Bounds and Fault-Recognition Limits for FO-Based KEMs
• Abstract summary: Black-box tests for Fujisaki-Okamoto decapsulation observe the sampled execution seen by the harness.<n>We study confirmation-code-augmented KEM variants under an honest-reference harness.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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^{-κ}$. 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 $α+β\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.

Related papers

• Sound and Efficient Certification of High-Quality Qubit Operations: Theory and Experiment [23.48673361417131]
  We introduce a sound black-box certification protocol for a single-qubit gate based on a small set of fixed, deterministic sequences.<n>From the data, the protocol derives finite-sample bounds on the gate's rotation eigenvalue, a gauge-invariant property.<n>We prove that these spectral constraints imply, up to a physically meaningful unitary change of basis, a rigorous average gate-fidelity lower bound for every time-independent qubit model.
  arXiv  Detail & Related papers  (2026-08-17T18:03:00Z)
• Information-theoretic limits on undetectable parameter-estimation attacks in continuous-variable quantum key distribution [1.7205106391379026]
  We formalize a certificate-forgery hypothesis test and identify its detectability with an information-theoretic rate.<n>Relative to a set $mathcalM$ of trusted observables, the forgery- detectability rate $g_mathcal M$ of a benign-statistics certificate is the missed-detection Stein exponent.
  arXiv  Detail & Related papers  (2026-07-25T23:36:36Z)
• Security Analysis for SCONE Logic Locking [8.289792786302579]
  SCONE [DAC'25] expands a logic locking interface with additional encoded inputs from the original primary inputs.<n>We show that both realizations are vulnerable, but for different reasons.<n>We propose a lightweight non-linear mitigation and show that it does not exhibit the vulnerabilities identified in this paper.
  arXiv  Detail & Related papers  (2026-07-03T12:57:29Z)
• Certified Finite-Shot Operating Windows for Virtual Distillation and Symmetry Verification [0.0]
  We develop a finite-shot operating-window theory that makes comparison certifiable for virtual distillation (VD) and symmetry verification (SV)<n>For VD, the law captures the statistical bias and denominator instability of its quotient estimator, with a concentration certificate locating the sample size beyond which the quotient is trustworthy.<n>For SV, it isolates the bias floor left by undetectable errors and the sampling penalty set by the acceptance probability.
  arXiv  Detail & Related papers  (2026-06-13T20:42:40Z)
• Imbuing Large Language Models with Bidirectional Logic for Robust Chain Repair [44.80087038178069]
  We introduce Teleological Reasoning Infilling (TRI), a training framework that endows decoder-only transformers with a native emphgoal-conditioned bridging capability.<n>At inference, TRI operates as a surgical repair module within a dual-system loop.<n>Experiments on three benchmarks demonstrate that TRI achieves state-of-the-art performance across all tasks, while reducing per-problem token expenditure by 31.2%.
  arXiv  Detail & Related papers  (2026-06-03T15:58:48Z)
• MEMSAD: Gradient-Coupled Anomaly Detection for Memory Poisoning in Retrieval-Augmented Agents [0.0]
  We formalize memory poisoning attacks on retrieval-augmented agents as a Stackelberg game with a unified evaluation framework.<n>We show faithful evaluation increases measured attack success by $4times$ (ASR-R: 0.25 to 1.00$)<n>Our primary contribution is MEMSAD, a calibration-based defense grounded in a gradient coupling.
  arXiv  Detail & Related papers  (2026-05-05T08:15:41Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Conformal Tradeoffs: Guarantees Beyond Coverage [0.02648566468224904]
  Deployed conformal predictors are long-lived decision infrastructure operating over finite operational windows.<n> Marginal coverage does not determine deployment-facing quantities.<n>We provide a framework for operational certification and planning beyond coverage.
  arXiv  Detail & Related papers  (2026-02-20T07:58:25Z)
• Reinforcement Learning with Verifiable yet Noisy Rewards under Imperfect Verifiers [90.50039419576807]
  Reinforcement Learning with Verifiable Rewards (RLVR) trains policies against automated verifiers to avoid costly human labeling.<n>To reduce vulnerability to verifier hacking, many RLVR systems collapse rewards to binary $0,1$ during training.<n>This choice carries a cost: it introduces textitfalse negatives (rejecting correct answers, FNs) and textitfalse positives (accepting incorrect ones, FPs)
  arXiv  Detail & Related papers  (2025-10-01T13:56:44Z)
• Unsupervised Conformal Inference: Bootstrapping and Alignment to Control LLM Uncertainty [49.19257648205146]
  We propose an unsupervised conformal inference framework for generation.<n>Our gates achieve close-to-nominal coverage and provide tighter, more stable thresholds than split UCP.<n>The result is a label-free, API-compatible gate for test-time filtering.
  arXiv  Detail & Related papers  (2025-09-26T23:40:47Z)
• Proof-Carrying Numbers (PCN): A Protocol for Trustworthy Numeric Answers from LLMs via Claim Verification [0.0]
  We propose textbfProof-Carrying Numbers (PCN), a presentation-layer protocol that enforces numeric fidelity through mechanical verification.<n>PCN is lightweight and model-agnostic, integrates seamlessly into existing applications, and can be extended with cryptographic commitments.
  arXiv  Detail & Related papers  (2025-09-08T17:20:16Z)
• Instance-Optimal Quantum State Certification with Entangled Measurements [1.8416014644193066]
  We prove nearly instance-optimal bounds for quantum state certification when the tester can perform fully entangled measurements.<n>We prove our lower bounds using a novel quantum analogue of the Ingster-Suslina method, which is likely to be of independent interest.
  arXiv  Detail & Related papers  (2025-07-08T14:15:46Z)
• Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
  Conformal prediction (CP) converts any model's output to prediction sets with a guarantee to cover the true label with (adjustable) high probability.<n>We propose a robust conformal prediction that produces smaller sets even with significantly lower MC samples.
  arXiv  Detail & Related papers  (2025-03-07T08:41:53Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.