A largely self-contained and complete security proof for quantum key distribution

Scope

• The analysis covers BBM92-like entanglement-based protocols and a prepare-and-measure protocol essentially equivalent to BB84.The manuscript treats the two protocol classes in separate parts after introducing security definitions and notation.Source: §1 · pp. 1, 3

Motivation

• Finite-resource QKD security remains difficult because earlier proofs did not provide convincing tradeoffs for finite signals, computation, and key lengths.Asymptotic proofs assume infinitely many signals and unbounded classical computation, while earlier finite-key bounds were insufficient for realistic key lengths.Source: §1 · pp. 1, 3

Protocol parameters

• Block length improves security and extraction efficiency but is limited by early key generation and the computational difficulty of processing longer strings.Typical implementations use block lengths around 10^5–10^6, while 10^7–10^8 may require extreme system stability over several hours.Source: §1 · p. 2

Security and performance

• Robustness measures the probability of obtaining a nontrivial key below a specified noise threshold and complements secrecy because an always-aborting protocol can be perfectly secure yet useless.The channel parameters where robustness vanishes provide a performance figure of merit for comparing protocols.Source: §1 · p. 2

Contribution

• The paper collects and clarifies prior entropic-uncertainty-based arguments into a complete, rigorous, and accessible security proof.It explicitly formalizes randomization, measurement, parameter estimation, error correction, privacy amplification, randomness, and communication transcripts.Source: §1 · pp. 2–3

Motivation

• Conditioning on non-abort events can introduce correlations that undermine intuitive symmetry arguments used to justify collective-attack reductions.Random basis choices and parameter-estimation sampling create symmetry, but abort thresholds require analyzing the state conditioned on protocol success.Source: §1 · p. 3

2 Formalism and notation

• The formalism assumes readers know the mathematical foundations of quantum information theory and introduces concepts needed for the main exposition and security proof.Sections 2.1–2.4 support the main exposition, while Section 2.5 concepts are used only in the security proof.Source: §2 · p. 3
• De Finetti reductions may require at least 10^5 or 10^6 channel uses before the key rate becomes effectively nonzero.This limits their practical usefulness for finite-resource security analyses.Source: §2 · p. 3
• A flaw identified in a previous protocol formalization illustrates why complete specification of every protocol component matters for security proofs.The cited flaw does not invalidate the earlier security guarantees but highlights the importance of rigorous formalization.Source: §2 · p. 3

2.1 Quantum systems, states and metrics

• Quantum systems are represented by finite-dimensional Hilbert spaces, with composite systems formed by tensor products and subsets indexed using Π_m,k.The notation includes dimensions |A|, ordered systems A[m], and k-element subsets of [m].Source: §2.1 · p. 4
• The section defines normalized and sub-normalized states, trace distance, purified distance, and their operational or contraction properties.Trace distance quantifies distinguishability, while purified distance is useful for sub-normalized states and contracts under quantum channels.Source: §2.1 · p. 4

2.2 Classical registers and events

• Classical random variables are modeled as quantum registers, including classical–quantum states and conditional states for events.The notation represents probabilities through projectors and supports conditioning on events and their complements.Source: §2.2 · pp. 4–5

2.3 Quantum channels and measurements

• Quantum channels are completely positive trace-preserving maps, and measurements are represented as channels that output classical registers.The section also defines diamond distance for channels and deterministic maps that retain the input register.Source: §2.3 · p. 5

2.4 Universal hash functions

• Universal2 hashing supports both error correction for correctness and privacy amplification for secrecy.The analysis requires no particular hash family, and suitable families exist when input and output cardinalities are powers of two.Source: §2.4 · p. 5

3 Formal description of the entanglement-based protocol

• The protocol’s formal description is organized through notation, a simple QKD protocol specification, and explicit mathematical operations for its constituent steps.The paper presents the nomenclature in Table 1 and the protocol overview in Table 2, with the precise model deferred to Section 3.3.Source: §3 · p. 7, Table 1 · p. 8, Table 2 · p. 10
• The protocol family assumes Alice and Bob initially share a quantum state and perform measurements locally, with sifting treated as free and biased settings excluded.The entanglement-based model uses shared quantum systems and does not allow measurement settings biased toward a specific value.Source: §3 · p. 7, §3.2 · p. 9

3.1 Assumptions of our model

• Security guarantees apply only under explicit assumptions, including finite-dimensional systems, sealed laboratories, trusted random seeds, authenticated communication, and deterministic detection.The text emphasizes that unmet implementation assumptions invalidate the derived guarantees; deterministic detection is acknowledged as unrealistic in practice.Source: §3.1 · pp. 7–8
• The model requires commuting measurements across up to m subsystems, so measurement order does not affect the resulting outcome distribution.Alice and Bob’s systems are decomposed into m individual subsystems, with binary generalized measurements on each subsystem.Source: §3.1 · p. 9
• Alice’s measurements must be sufficiently complementary, quantified by an average overlap c̄(m,n), with c̄ < 1 necessary for secrecy.The overlap can in principle be bounded experimentally under the commuting-measurement assumption; Bob requires no corresponding complementarity bound.Source: §3.1 · p. 9

3.2 Protocol parameters and overview

• The protocol is parameterized by block length m and sub-protocols for parameter estimation, error correction, and privacy amplification.The block length determines the number of shared quantum systems available for estimation and key extraction.Source: §3.2 · p. 9
• Parameter estimation uses k systems and tolerates error rate δ, leaving n := m−k systems for key generation.The estimation tuple is pe = {k, δ}, with k ≤ m and δ ∈ (0, 1/2).Source: §3.2 · p. 9
• Error correction is specified by syndrome length r, verification-hash length t, correction functions, and a hash family, without assuming a particular code structure.The error-correction scheme is represented by ec = {t, r, synd, corr, Hec}.Source: §3.2 · p. 10

4 Security of the generated key

• The ideal protocol may abort, but whenever it does not abort it outputs a uniformly random shared key, providing the reference for Δ-security.The real protocol is Δ-close to this ideal protocol in diamond distance.Source: §4 · p. 14, Table 3 · p. 15
• Security is established by bounding the real protocol’s output distance from the ideal output uniformly over all extensions ρABE, including an adversary-held system E.The relevant output trace distance is evaluated for arbitrary extensions of the shared state.Source: §4 · p. 15
• The proof separates correctness, requiring matching keys when both tests pass, from secrecy, requiring the accepted key to be independent of the adversary’s information.An auxiliary state with KB set equal to KA and the triangle inequality split the security criterion into two terms.Source: §4 · pp. 15–16
• The resulting security bound is Δm,pe,ec,pa ≤ εec + εpa.The error-correction and privacy-amplification parameters contribute additively to the overall security bound.Source: §4 · pp. 15–16

• Correctness is bounded by the error-correction hash length t, with failure probability ε_ec = 2^-t.Source: §5 · p. 16
• Secrecy combines parameter-estimation and privacy-amplification errors, whose tradeoff is controlled by the optimization parameter ν.Source: §5 · p. 16
• The total error consists of ε_pe, ε_ec, and ε_pa; choosing t = log(m), k = √m, and ν = log(m)^-1 makes the relevant components vanish asymptotically.Source: §5 · p. 16
• For robust operation at noise level δ, the error-correction leakage must satisfy r ≈ (m-k)h(δ).Source: §5 · p. 16
• The protocol achieves the asymptotically optimal Devetak–Winter rate as m grows, because k and log m become negligible compared with m.Source: §5 · p. 16

• The proof targets the probability that the protocol does not abort while producing distinct final keys.Source: §6.1 · p. 17
• Correctness follows by bounding unequal corrected strings through the collision probability of the error-correction hash.Source: §6.1 · p. 17
• An entropic uncertainty relation is applied using random basis registers and measurement maps to bound Alice’s smooth entropy conditioned on Bob’s outcomes.Source: §6.2 · pp. 17–18
• The statistical analysis removes unlikely parameter-estimation events by smoothing, with purified-distance disturbance bounded by the square root of the event probability.Source: §6.3 · pp. 18–19
• The sampling bound is distribution-independent and follows from random sampling without replacement together with Serfling’s inequality.Source: §6.3 · pp. 18–19
• After passing parameter estimation, the conditional max-entropy is bounded by (m-k)h(δ+ν), provided the smoothing condition holds.Source: §6.3 · p. 19
• The secrecy proposition combines the uncertainty, parameter-estimation, and leftover-hashing arguments to bound the final key’s deviation from an ideal secret key.Source: §6.4 · pp. 21–22

• The prepare-and-measure model includes registers for Alice’s raw key and Bob’s measurement results.Source: Prepare-and-measure protocol · p. 22
• Additional registers represent Alice’s and Bob’s basis-choice seeds, communicated seeds, and sifting information.Source: Prepare-and-measure protocol · p. 22
• The paper records this additional nomenclature in Table 4.Source: Table 4 · p. 22

7 Formal description of the prepare-and-measure protocol

• The prepare-and-measure protocol is essentially equivalent to BB84, and its security follows from the entanglement-based protocol under additional assumptions.Source: §7 · p. 22

7.1 Additional assumptions on preparation and measurement devices

• Alice and Bob need not share entanglement; instead, Alice prepares states sent through a quantum channel, making the setup more practical for metropolitan-scale key distribution.Source: §7.1 · p. 23
• The model retains finite-dimensional systems, sealed laboratories, random seeds, and authenticated communication while replacing commuting measurements, deterministic detection, and measurement complementarity assumptions.Source: §7.1 · p. 23
• Alice prepares independent round-by-round states based on a basis and bit input, with no basis information leaked by the prepared state.Source: §7.1 · p. 23
• The prepared states must satisfy a complementarity condition summarized by a constant c̄′ < 1, related to the entanglement-based complementarity constant.Source: §7.1 · p. 23
• The framework excludes weak-coherent-state BB84 implementations because their four states are linearly independent and violate the stated preparation assumption, although decoy-state modifications can restore security.Source: §7.1 · p. 23
• Bob’s measurement has conclusive outcomes 0 and 1 plus an inconclusive outcome ∅, representing effects such as photon loss or multiple detector clicks.Source: §7.1 · pp. 23–24

7.2 Protocol parameters and overview

• The protocol uses M prepared states with M ≥ m, typically scaling as 2m/η in optical implementations, and models an arbitrary finite-dimensional quantum channel between Alice and Bob.Source: §7.2 · p. 24, §7.3 · p. 24, Figure 8 · p. 24

Security result

• The reduction requires assumptions ensuring that Alice’s preparation leaks no basis information and Bob’s invalid outcomes are basis-independent.These assumptions enable the realistic protocol to be represented through a virtual state and measurement structure.Source: §8 · p. 29
• The prepare-and-measure protocol is secure whenever the corresponding entanglement-based protocol is ε-secure under matching device parameters.Theorem 13 establishes this security transfer directly.Source: §8 · p. 29

Performance

• The prepare-and-measure secret-key rate is defined as the key length ℓ divided by the number M of prepared states, rather than the entanglement-based block length m.This reflects the different sifting cost in the prepare-and-measure setting.Source: §8 · p. 29
• The sifting procedure is designed to simplify the analysis, not to maximize the secret-key rate or the ratio m/M.Alternative procedures could improve this rate and need not fix M in advance.Source: §8 · p. 29
• The expected prepare-and-measure key rate is η/2 times the simple protocol’s secret-key rate.The factor accounts for transmission η and the expected 50% basis agreement.Source: §8 · p. 29

Reduction

• Alice’s preparation assumptions allow the preparation process to be replaced by a measurement on a virtual extension of the average prepared state.This supplies the virtual state needed for the reduction to the entanglement-based protocol.Source: §9.1 · p. 30

Sifting and independence

• Bob’s measurement assumption ensures that successful sifting makes the retained basis seed SΦ independent of the shared quantum state.The resulting state factorizes into the protocol registers and a uniform seed.Source: §9.2 · pp. 30–31
• The sifting map depends on whether bases coincide, so uniformly random input bases yield a uniformly random retained string SΦ.Its invariance under simultaneous basis shifts explains why the seed does not depend on the detection subset.Source: §9.2 · p. 31

Protocol equivalence

• When sifting fails, the modified entanglement-based protocol aborts; when it succeeds, it produces the same output as the original entanglement-based protocol.The modified protocol is therefore less robust but preserves ε-security.Source: §9.3 · p. 32
• The prepare-and-measure protocol is represented as the modified entanglement-based protocol applied to a virtual state tensor-product with the uniform seed ρSΦ.The construction restricts the retained registers to the m indices selected by sifting.Source: §9.3 · p. 32

10 Conclusion

• The proof formalizes all protocol steps and explicitly states the assumptions required for security.The treatment covers the protocol through security analysis rather than isolating only individual components.Source: §10 · p. 33
• Practical secret key rates are achievable for BB84 and BBM92-like protocols with moderately large block sizes.Source: §10 · p. 33
• The reported security guarantees rely on assumptions that can be challenging to enforce in practice.The conclusion connects these assumptions to trade-offs between implementation ease and security guarantees.Source: §10 · p. 33
• The authors identify room to improve the trade-offs through closer collaboration between theory and experiment.Source: §10 · p. 33
• Future finite-resource analyses should extend beyond BB84 and BBM92, potentially using techniques beyond entropic uncertainty relations.For the six-state protocol, entropic uncertainty relations do not currently yield optimal asymptotic secret key rates, while tomography incurs large finite-key penalties.Source: §10 · p. 33

A Proof of entropic uncertainty relation in Proposition 4

• Proposition 4 considers a sub-normalized state with a classical register, a symmetry bijection, and a family of generalized measurements.Source: A Proof of entropic uncertainty… · p. 35
• The measurement map is represented by a Stinespring dilation isometry that retains measured and auxiliary registers.Source: A Proof of entropic uncertainty… · p. 35
• A purification on an auxiliary system enables the target inequality to be rewritten using smooth min- and max-entropy duality.Source: A Proof of entropic uncertainty… · p. 35
• A unitary rotation and an associated isometry coherently replace measurement in basis p with measurement in basis q(p).Source: A Proof of entropic uncertainty… · p. 36
• The remaining bound follows by selecting a nearby state for smooth min-entropy and applying data processing, purified-distance contraction, operator-norm bounds, and the target inequality.Source: A Proof of entropic uncertainty… · pp. 36–37
• The proof also uses the data-processing inequality to justify removing a purifying system from the cryptographic analysis.Source: A Proof of entropic uncertainty… · p. 36

B Proof of Leftover Hashing Lemma in Proposition 9

• The leftover hashing argument begins from a universal2 hash family mapping n-bit strings to ℓ-bit keys.Source: B Proof of Leftover Hashing Lemma in… · pp. 37–38
• The hashed output is compared with a fully mixed key state that is independent of the hash seed and adversarial system.Source: B Proof of Leftover Hashing Lemma in… · p. 37
• The proof first bounds the input state using conditional min-entropy and a state on the adversary's register.Source: B Proof of Leftover Hashing Lemma in… · p. 37
• Trace-distance analysis uses Schatten norms, Hölder's inequality, and the fact that the adversary's marginal is unchanged by hashing.Source: B Proof of Leftover Hashing Lemma in… · p. 37
• The fully mixed key state simplifies the operator expression, after which Jensen's inequality yields the desired bound.Source: B Proof of Leftover Hashing Lemma in… · p. 38
• The final step uses operator anti-monotonicity and the definition of the adversarial state to obtain the desired result.Source: B Proof of Leftover Hashing Lemma in… · p. 38
• Smoothing extends the bound from an entropy-optimizing nearby state to the original state using purified-distance monotonicity and trace-norm triangle inequalities.Source: B Proof of Leftover Hashing Lemma in… · p. 38