FVQKD: A Formal Verification of Quantum Key Distribution Security in Rocq

arXiv:2610.30645 · quant-ph, cs.CR, cs.LO · Submitted 2026-10-22 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai.

Mira: And I'm Mira, here with Lev.

Kai: We're looking at the paper: "FVQKD: A Formal Verification of Quantum Key Distribution Security in Rocq".

Mira: Here's the gist of the paper. Detailed Research Summary: FVQKD - A Formal Verification of Quantum Key Distribution Security in Rocq This research paper introduces FVQKD (Formal Verification of Quantum Key Distribution), a novel, reusable, and modular formal verification framework implemented as a Rocq library designed specifically for machine-checking the security proofs of Quantum Key Distribution (QKD) protocols.

Kai: The core contribution is establishing an end-to-end, kernel-checked chain connecting a formal protocol program to a composable finite-key epsilon-security statement at the tightest known bounds.

Mira: The framework is built upon a sophisticated foundation in mathematical logic and quantum information theory, leveraging tools such as Rocq for symbolic manipulation, MATHCOMP for algebraic reasoning, MATHCOMP-ANALYSIS for real analysis, and COQQ for finite-dimensional quantum theory.

Kai: Core Contributions of FVQKD 1.

Title and authors: Kai: So this paper is called FVQKD, which stands for Formal Verification of Quantum Key Distribution Security in Rocq. It’s about taking those complex security proofs from QKD protocols and checking them machine-checked using a library called Rocq.

Mira: Right, it's moving away from just hand-checking these proofs to having a systematic way to verify them against reasoning errors using formal tools. It suggests that we can build a reusable framework for this kind of analysis.

Lev: From an engineering standpoint, the main thing here is that they’re building something modular so you don't have to re-do the whole proof structure every time you look at a new protocol. That sounds like it would save a ton of time on actual hardware implementation checks later.

Kai: Exactly. The core contribution is setting up this end-to-end chain, connecting the formal protocol program all the way to a composable finite-key epsilon security statement at tight bounds. It’s about having that complete, verified path from the protocol down to the math.

Mira: I think what’s really compelling is how they reconstruct that entire proof infrastructure from first principles. They use things like the smooth entropy framework and the entropic uncertainty relation as explicit theorems you parameterize, which is a big deal for information-theoretic security proofs.

Lev: When you think about running this on real hardware, it means we could eventually plug in different QKD protocols—like decoy-state or measurement-device-independent ones—and have the verification engine handle the math automatically. The overhead would be in setting up that initial formal model, not in re-deriving the security bound every time.

Kai: And they did a really concrete thing with BB84, achieving a complete proof with zero incomplete proofs and only using three standard axioms from MATHCOMP-ANALYSIS for classical logic. That’s a solid result to show the chain works end-to-end.

Mira: That result is specifically at the tight bound established by Tomamichel et al., which means they're not just proving security, they're proving it against the best possible known adversary in that context. I mean, that’s a high bar to clear.

Lev: And what I find interesting about those three ingredients—the smooth entropic uncertainty relation, the Serfling sampling bound, and the Quantum Leftover Hash Lemma—is how they systematically break down the security analysis into these manageable pieces. That decomposition is key for making it usable.

Kai: It also clarifies some of those messy inconsistencies in the field regarding things like smoothing-ball metrics and witness domains for conditional entropies, which is useful context for anyone trying to compare different QKD analyses.

Mira: So, what does this actually change for us on the show? It means we can start treating formal verification as a standard tool instead of just an academic exercise when evaluating new QKD systems or protocols.

Title and authors: Lev: For someone who builds error correction, it suggests that the overhead of verifying these proofs is manageable because you have a proven structure to work from, which is better than having to invent the proof steps for every new scheme.

Kai: Ultimately, they show that machine-checking can reconstruct the complete proof infrastructure from first principles and uncover missing side conditions in published arguments. That's a powerful way to ensure rigor.

Mira: It’s about moving past just citing existing bounds and providing a mechanism to check those bounds against the protocol itself, which is a big step toward real-world assurance of QKD security.

Lev: For running this on hardware, it means we have a blueprint for what's required in terms of proof structure before you even start simulating the actual quantum states. It’s about formal specification driving hardware design.

Kai: So, to wrap up on FVQKD: it’s establishing that we can get an end-to-end, machine-checked QKD security proof for BB84 at Tomamichel et al.’s tight bound with zero incomplete proofs and only three standard axioms from MATHCOMP-ANALYSIS.

Mira: And I think the biggest implication is that this framework provides a reusable foundation for mechanizing the verification of other QKD protocols, which could be decoy-state or measurement-device-independent ones down the road.

Lev: It’s about having a blueprint for what's required in terms of proof structure before you even start simulating the actual quantum states, and that formal specification driving hardware design is where it lands for us.

Kai: So, we’ve looked at how FVQKD reconstructs the smooth entropy framework and EUR to establish bounds, and how they use the QLHL to bridge those bounds to practical steps like privacy amplification.

Mira: And they also showed that by fixing concrete parameters for BB84—like setting q=one n=k=one hundred four leak EC=one thousand twenty-four and security budgets epsilon = two-thirty-four and epsilon s = two-thirty-three —they get a specific, verifiable outcome.

Lev: That concrete parameterization is what makes it useful for hardware; you're not just looking at abstract theory, you’re looking at the exact numbers that would show up in your simulation or test setup.

Kai: And they also gave us some performance guarantees on privacy amplification, showing that the distance from uniformity of the post-hashed state is bounded by an expression involving epsilon' and a square root term with ((two ('H

HL: Z) over epsilon') two-one).

Mira: That bound on the key length optimization, where they derive an upper bound on the target key length based on protocol parameters and security budgets, is another piece of practical information we can use.

Lev: It's about having that upper bound on the target key length so you know exactly how much raw material you need to generate before you even start factoring in all the loss and error correction overhead.

The paper's summary: Kai: So this paper, FVQKD, essentially builds a formal verification framework using something called Rocq to check the security proofs for Quantum Key Distribution protocols like BB84 on a machine level.

Mira: Exactly, Kai. Instead of just reading about security bounds in papers from other people and trusting them, they're creating this reusable tool that lets you plug in a protocol and have the AI check if the proof chain holds up mathematically.

Lev: From my side, it’s about taking that whole analysis—the smooth entropy framework and all those other assumptions—and breaking it down into separate pieces you can verify one by one. That modularity is what I like because it makes troubleshooting much easier when we try to run these proofs on actual error-correction hardware.

Kai: Right, the big win here is that they managed to build this end-to-end chain, from the formal protocol code right down to a finite-key security statement at Tomamichel et al.'s tightest known bound for BB84.

Mira: That specific result is powerful because it shows zero incomplete proofs. They didn't just show it was secure; they provided the whole verifiable path with only three standard axioms from MATHCOMP-ANALYSIS for classical logic, which is pretty clean.

Lev: I mean, for running this on real hardware, that means we have a blueprint. We know exactly what kind of proof structure we need before we even start simulating the quantum states. It’s about formal specification driving the design, not just guessing how to write the error correction code later.

Kai: And they did this by systematically decomposing the security analysis into three main ingredients: that smooth entropy relation, a Serfling sampling bound for handling randomness, and a Quantum Leftover Hash Lemma to connect those bounds to things like privacy amplification.

Mira: That decomposition is key because it forces you to be explicit about every single assumption you make about the physical process—the sources, the measurements—which helps clear up all that confusion in the field about things like smoothing-ball metrics.

Lev: When we think about running this on real hardware, those ingredients tell us exactly where the overhead lands. The Serfling bound handles the sampling part efficiently, and that QLHL is what bridges the gap between pure information theory and your actual post-processing steps.

Kai: And they didn't just stop there with security; they also gave performance guarantees on privacy amplification, showing a bound on how far the final state is from being completely uniform after hashing.

Mira: That bound involves terms like epsilon' and an exponential part depending on the dimension of some hash space, which gives us a concrete idea of how much raw key length we need to target before factoring in all that error correction overhead Lev was talking about.

Kai: So, this paper really moves QKD security verification from just a theoretical exercise into a machine-checked process for BB84, showing that we can reconstruct the whole proof infrastructure from first principles.

Mira: And it sets a high bar by achieving that tight bound with zero incomplete proofs, which is what makes this framework so useful for anyone trying to rigorously verify other QKD protocols.

Lev: The real implication for hardware is that we get a blueprint for what's required in terms of proof structure before you even start simulating the actual quantum states.

Kai: We’ve seen how they use the smooth entropy and EUR to set the fundamental bounds, and how they use the QLHL to connect those bounds to practical post-processing steps like privacy amplification.

Mira: And by fixing concrete parameters for BB84, they give us a specific, verifiable outcome that lets us check if our actual system meets those conditions.

The paper's improvements: Tom: So we're looking at how the authors suggest improving their FVQKD framework and what that means for future work on QKD security analysis.

Kai: They’re actually suggesting a way to make this framework more general, moving it beyond just BB84 to handle other QKD protocols too.

Mira: Exactly, Kai. They want to focus on making the verification process truly modular so you can apply the same logic structure to decoy-state protocols or measurement-device-independent variants down the road.

Lev: From an error correction standpoint, that would be huge because right now it feels a bit like building a specific tool for one type of qubit and then trying to adapt it. A general framework means less custom coding when we move to more complex hardware setups.

Kai: They're aiming for something where you can define the protocol structure separately from the verification logic itself, making it easier to swap in different security assumptions without rewriting the entire engine.

Mira: And they’re pushing for a formal extraction method where you turn an informal description of a QKD protocol into a checked formal specification, ensuring it actually satisfies things like composable security across all those different adversaries.

Lev: That sounds like turning the whole verification process into an automated tool that checks requirements before we even start designing the physical layer circuits. It’s about catching flaws in the design phase instead of during expensive lab tests.

Kai: So, they want to build a system that can take a high-level protocol requirement and automatically check if it meets those mathematical security definitions using the Rocq library.

Mira: And they also want to address some of those tricky literature inconsistencies we mentioned earlier regarding things like smoothing-ball metrics by making the framework more explicit about which assumptions are actually necessary for a given security bound.

Lev: That means the next step is moving from proving one specific protocol to creating a library where different proof ingredients can be combined in novel ways. It’s building a toolkit rather than just writing one specific proof.

Kai: So, the direction they're heading is toward making FVQKD not just a single successful verification of BB84, but a reusable methodology for verifying any QKD scheme using this formal language and structure.

Mira: It seems like the future here is moving toward that automated protocol extraction mentioned earlier, where we can formally verify the design requirements before we even build it.

Lev: And for us in error correction, it means having a standardized way to check if our chosen post-processing steps—like privacy amplification—are actually sufficient given the information-theoretic bounds derived from this framework.

Kai: So, while they’ve shown what’s possible for BB84 now, the next goal is scaling that up so it can handle the complexity of modern QKD schemes in a truly systematic way.

Conclusion: Kai: So to wrap up, FVQKD is establishing that we can get an end-to-end, machine-checked QKD security proof for BB84 at Tomamichel et al.’s tight bound with zero incomplete proofs and only three standard axioms from MATHCOMP-ANALYSIS.

Mira: That’s the core result: a complete chain from the formal protocol to a composable finite-key epsilon security statement, which means we can finally machine-check these complex security arguments.

Lev: For me, it really shows that this kind of structured verification isn't just theoretical; it provides a real blueprint for what proof structure is needed when you move toward building out error correction systems for real hardware.

Kai: It’s about moving past just citing existing bounds and providing a complete, kernel-checked chain for BB84 security using the Rocq library.

Mira: And that framework is designed to be reusable, allowing researchers to formally verify other QKD protocols by decomposing the analysis into independent, verifiable proof ingredients.

Lev: That modularity is key because it means we don't have to re-derive the whole proof structure every time we look at a new scheme or a different type of physical implementation.

Kai: We’ve seen how they reconstruct the smooth entropy framework and EUR to establish bounds, and how they use the QLHL to bridge those bounds to practical steps like privacy amplification.

Mira: And they also showed that by fixing concrete parameters for BB84—like setting q=one and specific security budgets—they get a specific, verifiable outcome.

Kai: And they also gave us some performance guarantees on privacy amplification, showing a bound on how far the final state is from being completely uniform after hashing.

Mira: That bound on the key length optimization gives us an upper limit to target key lengths based on protocol parameters and security budgets, which is practical information for system design.

Lev: It's about having that upper bound so you know exactly how much raw material you need to generate before factoring in all the loss and error correction overhead.

Kai: So, FVQKD represents a significant advancement because it mechanizes the reconstruction of proof infrastructure from first principles for BB84 security.

Mira: It sets a standard for verification by providing that end-to-end, machine-checked QKD security proof with zero incomplete proofs and only three standard axioms from MATHCOMP-ANALYSIS.

Lev: The implication is that we get a blueprint for what's required in terms of proof structure before you even start simulating the actual quantum states.

Kai: We’ve looked at how they use the smooth entropy and EUR to set the fundamental bounds, and how they use the QLHL to connect those bounds to practical post-processing steps like privacy amplification.

Mira: And they also showed that by fixing concrete parameters for BB84, they get a specific, verifiable outcome that lets us check if our actual system meets those conditions.

Wrap-up: Kai: So, to wrap up, FVQKD is establishing that we can get an end-to-end, machine-checked QKD security proof for BB84 at Tomamichel et al.’s tight bound with zero incomplete proofs and only three standard axioms from MATHCOMP-ANALYSIS.

Kai: We’ve seen how they reconstruct the smooth entropy framework and EUR to set the fundamental bounds, and how they use the QLHL to bridge those bounds to practical steps like privacy amplification.

Kai: So, to wrap up on FVQKD: it’s establishing that we can get an end-to-end, machine-checked QKD security proof for BB84 with zero incomplete proofs and only three standard axioms from MATHCOMP-ANALYSIS.

Lev: For running this on hardware, it means we have a blueprint for what's required in terms of proof structure before you even start simulating the actual quantum states.

Ruixuan Deng, Zhengfeng Ji, Jiayu Zhang, Li Zhou

Tsinghua University · Zhongguancun Laboratory

quant-ph, cs.CR, cs.LO

Submitted: 2026-10-22

Updated: 2026-10-22

Comments: 87 pages: 12 pages of main text, 4 pages of references, and 71 pages of appendices. Artifact: https://github.com/fvqkd/FVQKD

Code: https://github.com/fvqkd/FVQKD

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: Detailed Research Summary: FVQKD - A Formal Verification of Quantum Key Distribution Security in Rocq This research paper introduces FVQKD (Formal Verification of Quantum Key Distribution), a novel,

Key concepts

FVQKD: A novel, modular framework built on Rocq designed to formally verify QKD security. It connects a formal protocol program directly to a mathematical statement about finite-key security, ensuring every step of the proof is machine-checked.
Smooth Entropy Framework: This framework explicitly incorporates Renner's smooth entropy concept. It is essential for deriving tighter bounds on key secrecy by rigorously defining how uncertainty and entropy relate in quantum information analysis.
Quantum Leftover Hash Lemma (QLHL): A critical mathematical tool used to decompose the complex security analysis of QKD. The QLHL bridges the gap between abstract information-theoretic bounds and practical steps like privacy amplification, ensuring a complete proof chain.

Terminology

Formal Verification — 1× in this paper · explained in 2 episodes
Verification — 1× in this paper · explained in 2 episodes

Summary

Detailed Research Summary: FVQKD - A Formal Verification of Quantum Key Distribution Security in Rocq

This research paper introduces FVQKD (Formal Verification of Quantum Key Distribution), a novel, reusable, and modular formal verification framework implemented as a Rocq library designed specifically for machine-checking the security proofs of Quantum Key Distribution (QKD) protocols. The core contribution is establishing an end-to-end, kernel-checked chain connecting a formal protocol program to a composable finite-key epsilon-security statement at the tightest known bounds.

The framework is built upon a sophisticated foundation in mathematical logic and quantum information theory, leveraging tools such as Rocq for symbolic manipulation, MATHCOMP for algebraic reasoning, MATHCOMP-ANALYSIS for real analysis, and COQQ for finite-dimensional quantum theory.

Core Contributions of FVQKD

The paper presents two primary contributions:

A Reusable Formal Verification Framework: FVQKD provides a modular structure allowing researchers to formally verify QKD security proofs by decomposing the analysis into independent, verifiable proof ingredients.
An End-to-End Machine-Checked Proof for BB84: The framework successfully establishes a complete, kernel-checked chain from the formal protocol program to a composable finite-key epsilon-security statement for the BB84 protocol, achieving security at the tight bound established by Tomamichel et al. [10]. Crucially, this result is presented with zero incomplete proofs and relies only on three standard axioms inherited from MATHCOMP-ANALYSIS for classical logic.

Mathematical and Theoretical Underpinnings

The security analysis within FVQKD is grounded in a rigorous information-theoretic framework that exposes every source and measurement assumption as an explicit theorem parameter. This foundation includes:

Smooth Entropy Framework: The framework explicitly incorporates the smooth entropy framework of Renner [9], which is essential for deriving tighter bounds on key secrecy.
Entropic Uncertainty Relation (EUR): The analysis utilizes the EUR to relate the conditional min-entropy of key registers to the overlap of measurement operators, providing a fundamental lower bound on achievable security.
Quantum Leftover Hash Lemma (QLHL): This lemma is employed as a critical component in decomposing the security analysis.
Serfling Sampling Bound: This bound is integrated into the proof ingredients to handle sampling aspects of the protocol efficiently.

The main theorem (Theorem 10) formalizes the security conclusion for BB84: under specific conditions relating error correction leakage, verification hash length, and privacy amplification relative to a defined security budget, the protocol is epsilon tot-secure. The mathematical statement concludes that the output registers satisfy: S (E E pub), (E E pub) F, and (E E pub) Z.

Detailed Security Analysis Components

The security analysis is systematically decomposed into three independent proof ingredients, which are the building blocks of the end-to-end verification:

Smooth Entropic Uncertainty Relation: This ingredient provides a lower bound on the secure key rate by explicitly parameterizing all source and measurement assumptions.
Serfling Sampling Bound: This addresses the probabilistic aspects of the protocol execution, ensuring that sampling procedures do not compromise security beyond established limits.
Quantum Leftover Hash Lemma (QLHL): This lemma is used to bridge the gap between the information-theoretic bounds and practical post-processing steps like privacy amplification.

The framework also addresses literature inconsistencies by identifying competing conventions across the field regarding smoothing-ball metrics and witness domains for conditional entropies, providing necessary clarification for rigorous comparison.

Protocol Verification Specifics (BB84 Instance)

The verification process is instantiated using concrete parameters derived from the BB84 protocol structure:

Protocol Context: The analysis fixes a protocol P, an overlap parameter q, a certified device, an external register space, and a round budget M = round_limit(P).
Formal Endpoint Definition: The formal endpoint is defined by fixing the protocol, overlap parameter, certified device, external register space, and round budget.
Protocol Security Theorem (Theorem 10): This theorem precisely defines the conditions under which the protocol is epsilon tot-secure: The protocol is epsilon tot-secure when it is epsilon c-correct and epsilon s-secret with epsilon c + epsilon s epsilon tot.
Concrete Parameters: A specific instance uses parameters such as q=1, n=k=104, Q tol=10-2, leak EC=1024, and security budgets epsilon = = epsilon c = 2-34 and epsilon s = 2-33. The fixed round budget is M = 100(n+k) = 2,000,000, with a certified instance length of l=2000.

Key Performance Bounds

Beyond the primary security proof, the framework yields crucial performance guarantees:

Privacy Amplification Bound: A corollary demonstrates that for a state rho XE that is psdlf (perfectly separable distributed light field), the distance from uniformity of the post-hashed state is bounded by:

dist_from_uniform(post-hash-state) epsilon' + (2-1) -1 sqrt ((2 ('H[HL] Z) over epsilon') 2-1)

Key Length Optimization: A lemma establishes an upper bound on the target key length (target) based on the protocol parameters, security budget epsilon s, and round budget M. This bound is found by optimizing over the privacy amplification parameter epsilon and the error parameter.

Concluding Significance

FVQKD represents a significant advancement in QKD security verification. By mechanizing the reconstruction of proof infrastructure from first principles (smooth entropy, EUR, QLHL), it moves beyond simply citing existing bounds to providing a complete, kernel-checked chain for BB84 security. The final conclusion asserts that FVQKD provides the first end-to-end, machine-checked QKD security proof: composable finite-key BB84 security at Tomamichel et al.’s tight bound [10], with zero incomplete proofs and only three standard axioms inherited from MATHCOMP-ANALYSIS for classical logic. This framework is positioned to serve as a foundational methodology for verifying the security of a wide range of QKD protocols, including decoy-state and measurement-device-independent variants.

Improvements for AI systems

Machine-checked security verification for quantum key distribution protocols can be achieved by formalizing protocol execution using a small programming language with classical and quantum variables as distinct types, allowing properties like correctness and secrecy to be stated as formal theorems rather than relying on informal analysis.
The improved AI system can formally verify the end-to-end composable finite-key security for protocols like BB84 by reconstructing the complete proof infrastructure from first principles, including the smooth entropy framework, the entropic uncertainty relation, and the Quantum Leftover Hash Lemma.
The system can systematically expose necessary side conditions that published arguments leave unstated, such as a missing proof branch in an analysis on which later finite-key proofs build, ensuring that every assumption is explicitly stated and discharged during verification.
The AI can provide a formal framework for protocol extraction, turning informal protocol specifications into checked formal specifications by verifying they satisfy requirements like the Composable security definition across all adversaries and attack strategies.