Composable Security of QKD

Quantum key distribution promises information-theoretic security, but a proof is only as trustworthy as the criterion it certifies — and for a decade the field certified the wrong thing. Early proofs bounded Eve's accessible information $I_{\mathrm{acc}}(X;E)$ , the most classical mutual information she can wring from her quantum side-information by measuring it. That criterion is seductive and wrong: it protects a key only against an adversary who measures immediately, while a real adversary can keep her quantum memory in cold storage and choose her measurement later — after watching how the key is used, for instance after seeing a ciphertext the key encrypted. A key certified "secure" this way can leak completely the moment it is put to work. Composable security repairs the definition. It compares the real classical-quantum state $\rho_{KE}$ of the key $K$ and Eve's system $E$ against an ideal state $\tau_K\otimes\rho_E$ , in which the key is perfectly uniform and utterly decoupled from Eve. The gap is measured in trace distance, and the key is $\varepsilon$ -secure when that distance is at most $\varepsilon$ . Trace distance is the right ruler because it equals the maximum probability any test — including one invented after the fact — can distinguish real from ideal. An $\varepsilon$ -secure key therefore behaves like a perfect key in every environment, failing at most with probability $\varepsilon$ . Formally this lives in the Abstract Cryptography of Maurer and Renner and the equivalent Universal Composability of Canetti: a real protocol constructs an ideal key resource to within $\varepsilon$ , and the composition theorem guarantees that swapping real for ideal anywhere costs at most $\varepsilon$ . Quantitatively the extractable key length is governed by the smooth min-entropy $H_{\min}^{\varepsilon}(X|E)$ through the Leftover Hashing Lemma, reducing asymptotically to the Devetak–Winter rate. This one framework welds the security definition, the machinery of one-shot quantum information, and concrete protocols like BB84 and E91 into a single accounting system.

Key takeaways

Composable security certifies that a QKD key is interchangeable with an ideal uniform key in any later use, failing only with probability $\varepsilon$ — measured as trace distance from an ideal key resource.
The correct figure of merit is not Eve's accessible or Holevo information but $\tfrac12\lVert\rho_{KE}-\tau_K\otimes\rho_E\rVert_1\le\varepsilon$ , the only quantity that composes safely with downstream protocols.
Because trace distance is monotone under any process and obeys the triangle inequality, errors add: a QKD stack is at most $\varepsilon_{\mathrm{tot}}\le\sum_i\varepsilon_i$ -insecure.
The achievable secret length follows the Leftover Hashing Lemma, $\ell=H_{\min}^{\varepsilon_s}(X|E)-\mathrm{leak}_{\mathrm{EC}}-2\log\frac{1}{2\varepsilon_h}$ , net of reconciliation leakage.
The flawed accessible-information criterion fails precisely because Eve can delay her measurement until she learns how the key is used; trace distance forbids that gain.
Asymptotically the rate collapses to Devetak–Winter, $r_\infty=I(X;Y)-I(X;E)$ ; for BB84 this gives a positive key up to a QBER of about 11%.
Key idea: Security must be defined as closeness — in trace distance — between the real key-and-eavesdropper state and an ideal state with a uniform key decoupled from Eve. Because trace distance equals the maximum distinguishing advantage and obeys the triangle inequality, this single quantity composes: an $\varepsilon$ -secure key is universally substitutable for an ideal one, with failures adding at most linearly.

The core insight

Security must be defined as closeness — in trace distance — between the real key-and-eavesdropper state and an ideal state with a perfectly uniform key decoupled from the eavesdropper. Because trace distance equals the maximal distinguishing advantage and obeys the triangle inequality, this one quantity composes: an $\varepsilon$ -secure key is universally substitutable for an ideal key, with failures adding at most linearly.

Where this lives today

Composable security is no longer a theorem on a chalkboard; it is the number on a datasheet. Commercial QKD systems from vendors such as ID Quantique and Toshiba, and the satellite links of the Chinese quantum network (the Micius demonstrations), specify their keys with an explicit composable $\varepsilon\sim 10^{-9}$ from finite blocks of $10^6$ to $10^9$ signals — the tight Tomamichel–Lim–Gisin–Renner analysis converts raw counts into a certified length, and ETSI's QKD group writes composable security into its standards. The frontier is device-independent QKD, certified from a Bell-inequality violation without trusting the boxes (first loophole-free demonstrations in 2022), and measurement-device-independent QKD, immune to detector attacks; in both, the smooth min-entropy is bounded directly from the statistics and the same criterion carries through unchanged. Composability is also the accounting language of the quantum internet: keys stitched from many entanglement-swapped links inherit an additive $\sum_i\varepsilon_i$ budget, letting a network quote one end-to-end number.

The physical picture

Hand your freshly minted key to an all-powerful referee who also holds Eve's quantum memory and may run any test he can imagine — now, tomorrow, or after watching the key encrypt a message. Composable $\varepsilon$ -security is the promise that no such test tells your key from a fresh uniform string with advantage above $\varepsilon$ . The strength of the guarantee is what it quantifies over: every test, including ones nobody has invented yet — exactly what a general-purpose key needs, since it gets dropped into unknown larger systems. The older accessible-information criterion collapses on timing. Eve entangles a probe with the raw key and waits. When you one-time-pad a message and broadcast $c=m\oplus K$ , that ciphertext tells her which measurement on her stored probe is most revealing — so she measures then, not before. Accessible information silently assumed she committed up front; trace distance makes deferral worthless because it bounds the whole joint state, not one measurement's statistics. The first figure draws the two worlds the referee must distinguish.

Figure

Composable security compares two worlds: the real state ρ_KE where the key K may stay correlated with Eve, versus the ideal state τ_K ⊗ ρ_E with a uniform key fully decoupled from Eve. No referee D separates them with advantage beyond the trace distance ½‖ρ_KE − τ_K⊗ρ_E‖₁ ≤ ε

Once the definition is fixed, the quantitative question is how many perfectly secret bits we can squeeze out. The answer is the smooth min-entropy $H_{\min}^{\varepsilon}(X|E)$ — a worst-case, single-shot cousin of conditional entropy measuring how much of the raw key Eve provably cannot predict. Privacy amplification hashes the partially-secret raw key down to nearly that many decoupled bits, minus reconciliation's leaked syndrome. For BB84 under one-way reconciliation this predicts a positive key up to a bit-error rate near 11%, which the second figure plots.

Figure

The BB84 asymptotic secret fraction r = 1 − 2h(Q) versus the quantum bit-error rate Q. The rate falls from r = 1 at Q = 0 to r = 0.427 at Q = 0.05 and vanishes at the threshold Q ≈ 0.11, above which no composable key can be distilled by one-way reconciliation

The core equations

Composability begins with a definition, not a theorem: a key is $\varepsilon$ -secure when its real joint state with the eavesdropper is $\varepsilon$ -close in trace distance to the ideal decoupled state. Everything downstream follows from this one line.

d\big(K\,|\,E\big)\;:=\;\tfrac12\big\lVert \rho_{KE}-\tau_K\otimes\rho_E\big\rVert_1\;\le\;\varepsilon \qquad (1)

where: $\rho_{KE}$ — real joint classical-quantum state of the key $K$ and Eve's system $E$ ; $\tau_K=\frac{1}{|K|}\sum_k|k\rangle\langle k|$ — maximally mixed (uniform) key, the ideal target; $\rho_E$ — reduced state of Eve, $\mathrm{Tr}_K\rho_{KE}$ ; $\lVert\cdot\rVert_1$ — trace norm, $\lVert A\rVert_1=\mathrm{Tr}\sqrt{A^\dagger A}$ ; $\varepsilon$ — security parameter. Reading it: the key is uniform and independent of Eve except with weight $\varepsilon$ , a real failure probability. The definition is meaningful only because trace distance has a hard operational identity: the largest probability, over every two-outcome test, of telling the two states apart.

\tfrac12\lVert\rho-\sigma\rVert_1=\max_{0\le P\le\mathbb{1}}\,\mathrm{Tr}\big[P(\rho-\sigma)\big] \qquad (2)

where: $P$ — any measurement effect, $0\le P\le\mathbb{1}$ , one outcome of a two-outcome POVM; $\rho,\sigma$ — the states being distinguished (real vs. ideal). Reading it: no test beats advantage $\tfrac12\lVert\rho-\sigma\rVert_1$ — so bounding this bounds every adversary at once. Substitution makes a key reusable — the literal meaning of "composable": if the real key is $\varepsilon$ -close to ideal, any application consuming it behaves within $\varepsilon$ of how it would with a perfect key.

d\big(K\,|\,E\big)\le\varepsilon\ \Longrightarrow\ \big|\Pr[\mathcal{D}\ \text{wins, real}]-\Pr[\mathcal{D}\ \text{wins, ideal}]\big|\le\varepsilon \qquad (3)

where: $\mathcal{D}$ — any distinguishing environment or downstream protocol using the key. Reading it: swap the real key for an ideal one anywhere and the system's observable behaviour shifts by at most $\varepsilon$ — licence to reason as if the key were perfect. Real QKD is a stack of sub-protocols — sifting, estimation, reconciliation, privacy amplification, authentication — each secure to its own parameter. The triangle inequality lets their failures be summed rather than compounded.

\varepsilon_{\mathrm{tot}}\;\le\;\sum_i\varepsilon_i \qquad (4)

where: $\varepsilon_i$ — security parameter of the $i$ -th sub-protocol; $\varepsilon_{\mathrm{tot}}$ — composable security of the assembled protocol. Reading it: the budget is a simple sum, allocated across stages like a tolerance stack. The extractable key length is set by privacy amplification through the Leftover Hashing Lemma: two-universal hashing turns a raw key of known smooth min-entropy into nearly-uniform decoupled bits, minus reconciliation leakage and a small hashing tax.

\ell\;=\;H_{\min}^{\varepsilon_s}(X|E)\;-\;\mathrm{leak}_{\mathrm{EC}}\;-\;2\log\frac{1}{2\varepsilon_h} \qquad (5)

where: $\ell$ — extractable $(\varepsilon_s+\varepsilon_h)$ -secure bits; $H_{\min}^{\varepsilon_s}(X|E)$ — smooth conditional min-entropy of raw key $X$ given Eve; $\mathrm{leak}_{\mathrm{EC}}$ — bits revealed in reconciliation, at least $n\,h(Q)$ with $Q$ the QBER; $\varepsilon_s,\varepsilon_h$ — smoothing and hashing parameters. Reading it: keep what Eve is provably ignorant of, minus a small hashing deposit. The smooth min-entropy is built from the plain conditional min-entropy: the negative log of how small Eve's guessing operator can be while still dominating the joint state.

H_{\min}(X|E)_{\rho}=-\log\min\big\{\,\mathrm{Tr}\,\sigma_E\;:\;\rho_{XE}\le\mathbb{1}_X\otimes\sigma_E\big\} \qquad (6)

where: $\sigma_E$ — any positive operator on Eve's system in the minimization; $\rho_{XE}$ — classical-quantum state of raw key and eavesdropper. Reading it: $2^{-H_{\min}(X|E)}$ is essentially Eve's optimal probability of guessing $X$ from $E$ . In the asymptotic limit of many i.i.d. signals the apparatus collapses to a single rate: Alice–Bob information minus Alice–Eve information.

r_\infty\;=\;H(X|E)-H(X|Y)\;=\;I(X;Y)-I(X;E) \qquad (7)

where: $I(X;Y)$ — Alice–Bob mutual information, setting reconciliation cost; $I(X;E)$ — Alice–Eve Holevo information, setting privacy-amplification cost; $r_\infty$ — asymptotic composable secret-key rate per signal under collective attacks. Reading it: you keep what you share with Bob but not Eve — the Devetak–Winter formula, the large- $n$ limit of the finite-key length.

Derivation AWhy accessible information fails to compose

The goal is to exhibit, concretely, an eavesdropper for whom the accessible-information criterion certifies a "secure" key that is in fact wide open, and to show only the trace-distance criterion sees the danger. The mechanism is deferral: the criterion that assumes Eve measures early is blind to the distinguishing power she gains once she learns how the key is used. We build the malicious state, compute what accessible information sees, then show the ciphertext hands Eve her missing side-information.

Step 1. Prepare the joint state $\rho_{KE}=\tfrac12|0\rangle\langle0|_K\otimes\rho_E^0+\tfrac12|1\rangle\langle1|_K\otimes\rho_E^1$ , where $\rho_E^0,\rho_E^1$ are probe states almost indistinguishable by any single fixed measurement yet separable once a classical hint selects the right basis. Why: build correlation invisible to an early measurement but latent in the global state — the case the two criteria disagree on.

Step 2. Evaluate accessible information $I_{\mathrm{acc}}(K;E)=\max_{\{M\}}I(K;\hat K)$ , the mutual information after Eve's best fixed measurement. For suitably conjugate $\rho_E^0,\rho_E^1$ this is tiny, so the criterion declares the key secure. Why: it optimizes over measurements chosen with no knowledge of downstream use, so it cannot see correlation only a later measurement reveals.

Step 3. Now let the key encrypt a message by one-time pad, publishing $c=m\oplus K$ . That public string tells Eve which measurement best discriminates $\rho_E^0$ from $\rho_E^1$ ; measuring after seeing $c$ , she recovers $K$ far better than her early-measurement bound allowed. Why: the ciphertext is the side-information accessible information ignored — deferral converts latent correlation into extracted key.

Step 4. Contrast the trace distance $d(K|E)=\tfrac12\lVert\rho_{KE}-\tau_K\otimes\rho_E\rVert_1$ , computed from the global state and indifferent to when Eve measures; it stays large. Why: it bounds every process at once (equation 2), already accounting for the delay — so it, not accessible information, composes.

Go deeper · Derivation B · 1 minFrom smooth min-entropy to extractable key

Derivation BFrom smooth min-entropy to extractable key

The goal is to derive the number of $\varepsilon$ -secure bits privacy amplification yields from a raw key of known smooth min-entropy — the Leftover Hashing Lemma underwriting equation (5). We hash with a random two-universal function, bound the output's distance from ideal by a collision (Rényi-2) entropy, then trade collision entropy for smooth min-entropy, giving a tight formula linking output length, min-entropy, and security parameter.

Step 1. Choose the extractor $K=F(X)$ with $F$ from a two-universal family $\mathcal{F}$ mapping $X$ to $\{0,1\}^\ell$ , the seed $F$ public and appended to Eve's system; two-universality means $\Pr_F[F(x)=F(x')]\le 2^{-\ell}$ for $x\ne x'$ . Why: publishing the seed keeps Eve maximally informed, so security holds even though she knows the hash.

Step 2. Bound the trace distance to ideal by the Hilbert–Schmidt norm via Cauchy–Schwarz, $d\le\tfrac12\sqrt{2^\ell\,\mathbb{E}_F\,\mathrm{Tr}[(\rho_{F(X)E}-\tau\otimes\rho_E)^2]}$ , moving from the intractable 1-norm to a computable 2-norm averaged over the seed. Why: the quadratic 2-norm opens up to the hash family's pairwise-collision structure that the 1-norm hides.

Step 3. Expand the average; two-universality cancels all cross terms, leaving $\mathbb{E}_F\,\mathrm{Tr}[\cdots]\le 2^{-H_2(X|E)}$ , the conditional collision entropy $H_2$ , so $d\le\tfrac12\,2^{-\frac12(H_2(X|E)-\ell)}$ . Why: the collision property of $\mathcal{F}$ turns an unwieldy sum into a single entropy.

Step 4. Replace $\rho$ by the nearby min-entropy-maximizing state: since $H_2\ge H_{\min}$ and smoothing costs $\varepsilon_s$ , $\tfrac12\lVert\rho_{F(X)EF}-\tau_\ell\otimes\rho_{EF}\rVert_1\le\tfrac12\,2^{-\frac12(H_{\min}^{\varepsilon_s}(X|E)-\ell)}+\varepsilon_s$ . Setting $\ell=H_{\min}^{\varepsilon_s}(X|E)-2\log\frac{1}{2\varepsilon_h}$ forces the first term to $\varepsilon_h$ , so the key is $(\varepsilon_s+\varepsilon_h)$ -secure. Why: smoothing tolerates rare bad events; the choice of $\ell$ solves the exponential for the target error.

Go deeper · Derivation C · 1 minComposing the full QKD stack

Derivation CComposing the full QKD stack

The goal is to assemble one composable security parameter for an entire QKD protocol from the parameters of its stages — estimation, reconciliation, privacy amplification, authentication — and to see why the classical channel must be authenticated. We split the guarantee into correctness and secrecy, attach the authentication cost, and add everything by the triangle inequality — the finite-key budget vendors quote.

Step 1. Correctness: reconciliation plus a hash-based error-verification step guarantees $\Pr[K_A\ne K_B]\le\varepsilon_{\mathrm{cor}}$ . Why: a key the parties disagree on is not substitutable for an ideal shared key, however secret.

Step 2. Secrecy: privacy amplification (costing $\varepsilon_s+\varepsilon_h$ ) on a min-entropy bound certified by parameter estimation ( $\varepsilon_{\mathrm{PE}}$ ) gives $\varepsilon_{\mathrm{sec}}\le\varepsilon_{\mathrm{PE}}+\varepsilon_s+\varepsilon_h$ . Why: the min-entropy fed to the hash is only as trustworthy as the channel estimate, so estimation's failure probability is paid explicitly.

Step 3. Authentication: the classical channel is "free" only if authenticated by an $\varepsilon_{\mathrm{auth}}$ -secure MAC, adding $+\varepsilon_{\mathrm{auth}}$ ; without it a man-in-the-middle runs two half-protocols and composition collapses. Why: an unauthenticated channel lets Eve impersonate the parties, which no quantum secrecy repairs.

Step 4. Aggregate by the triangle inequality: $\varepsilon_{\mathrm{QKD}}\le\varepsilon_{\mathrm{cor}}+\varepsilon_{\mathrm{sec}}+\varepsilon_{\mathrm{auth}}$ , so the protocol $\varepsilon_{\mathrm{QKD}}$ -constructs an ideal key resource, with typical targets $10^{-9}$ to $10^{-10}$ . Why: one honest failure probability for the whole machine, by simple addition, is what composability buys.

Limiting cases

Case	Result	Meaning
Ideal decoupling	$\tfrac12\lVert\rho_{KE}-\tau_K\otimes\rho_E\rVert_1=0$	The key is perfectly uniform and independent of Eve — the ideal resource with $\varepsilon=0$ ; unattainable at finite $n$ but approached as $n\to\infty$ .
Asymptotic i.i.d. rate	$r=\lim_{n\to\infty}\frac{\ell}{n}=H(X\|E)-H(X\|Y)$	The Devetak–Winter rate: the collective-attack secret fraction is Eve's conditional-entropy deficit minus the reconciliation cost.
BB84 threshold QBER	$r_{\mathrm{BB84}}=1-2h(Q)$ , so $r=0$ at $Q\approx 11\%$	One-way reconciliation yields a positive composable key only below a bit-error rate of about $0.110$ ; above it, distillation fails.
Finite-key correction	$\ell\approx n\,r-O(\sqrt{n})$	For finite block length the length drops below the asymptotic rate by a $\sqrt{n}$ statistical penalty from parameter estimation and smoothing.

Common trapBounding Eve's accessible information proves composable security

It does not. Accessible (Holevo) information presumes Eve measures her quantum memory before the key is used, committing to a fixed measurement in advance. A patient adversary who keeps her state intact and measures only after seeing how the key is used — for instance after a ciphertext is broadcast — extracts far more than any accessible-information bound suggests, because the later side-information tells her which measurement to make. This is not a corner case: it is generic for any key that will actually be used. Only the trace-distance criterion (equivalently, a smooth min-entropy bound) forbids this deferral gain, and only it survives composition. A proof that bounds $I_{\mathrm{acc}}(X;E)$ and stops there has proved the wrong theorem.

Worked examples

1 · Extractable key length from a min-entropy bound (fully worked)

A reconciled raw key has smooth min-entropy $H_{\min}^{\varepsilon_s}(X|E)=400$ bits; reconciliation leaked $120$ bits. With hashing error $\varepsilon_h=2^{-30}$ , how many composably secure bits can be extracted, and to what security?

Step 1. Compute the hashing tax $2\log\frac{1}{2\varepsilon_h}$ . Here $\frac{1}{2\varepsilon_h}=\frac{1}{2\cdot 2^{-30}}=2^{29}$ , so $\log\frac{1}{2\varepsilon_h}=29$ and the tax is $2\times 29=\mathbf{58}$ bits.

Step 2. Subtract everything Eve might know or the parties revealed: $\ell=400-120-58=\mathbf{222}$ bits.

Step 3. The output is $(\varepsilon_s+\varepsilon_h)$ -close to an ideal 222-bit key, with $\varepsilon_h\approx 10^{-9}$ . Result: $\ell=222$ secure bits. Nearly 45% of the min-entropy is spent on leakage and tax — why short-block QKD is so length-starved.

2 · The BB84 error-rate threshold (fully worked)

The asymptotic BB84 secret fraction under one-way reconciliation is $r=1-2h(Q)$ , $h$ the binary entropy. Find the rate at $Q=5\%$ and the tolerable-error threshold.

Step 1. Evaluate the binary entropy at $Q=0.05$ : $h(0.05)=-0.05\log_2 0.05-0.95\log_2 0.95=0.2161+0.0703=\mathbf{0.2864}$ bits.

Step 2. Insert into the rate: $r=1-2h(0.05)=1-0.5728=\mathbf{0.427}$ secret bits per sifted bit — a noisy channel still yields a good key.

Step 3. The threshold is where $r=0$ , i.e. $h(Q)=\tfrac12$ : solving gives $Q\approx 0.110$ , since $h(0.11)=0.3503+0.1496\approx 0.5$ . Result: $r=0.427$ at $Q=5\%$ , vanishing at $Q\approx 11\%$ . Above 11% Eve can hold as much information as Bob, and no composable key survives one-way processing — the red threshold line in the second figure.

3 · Adding up a security budget

A protocol has $\varepsilon_{\mathrm{cor}}=10^{-12}$ , $\varepsilon_{\mathrm{PE}}=10^{-10}$ , $\varepsilon_s=10^{-10}$ , $\varepsilon_h=2^{-30}\approx 10^{-9}$ , $\varepsilon_{\mathrm{auth}}=10^{-12}$ . Find the overall composable security.

Step 1. By additive composition (equation 4) the total is the sum, dominated by the hashing error $\varepsilon_h\approx 10^{-9}$ . Result: $\varepsilon_{\mathrm{QKD}}\approx 1.2\times 10^{-9}$ , inside a typical $10^{-9}$ target — budget the largest term first, since the weakest stage sets the scale.

Physics of the portrait

Composable security is a young idea with a clear architect: the trace-distance criterion, the smooth entropies that make it computable, and the composition theorem were forged in the mid-2000s, chiefly by Renato Renner, on Canetti's classical Universal Composability.

Origins · 1 minRenato Renner and how this was discovered

Renato Renner

born 1974 · composable security and one-shot quantum information theory

Renato Renner is the physicist who put quantum key distribution on a rigorous, composable footing. In his 2005 ETH Zurich doctoral thesis, Security of Quantum Key Distribution, he demolished the then-standard accessible-information criterion by showing it does not compose — a "secure" key by that measure can leak the moment it is used — and replaced it with the trace-distance criterion canonical ever since. To make it computable he introduced the smooth min- and max-entropies, one-shot quantities that tame finite, correlated, non-i.i.d. data and reduce to the von Neumann entropy only asymptotically; with König and Maurer he proved the quantum Leftover Hashing Lemma anchoring privacy amplification against a quantum adversary. His work joined Canetti's Universal Composability (2001) to the operational quantum information of Devetak and Winter — whose 2005 rate $I(X;Y)-I(X;E)$ is the asymptotic limit of Renner's finite-key length. Later, with Tomamichel, Lim and Gisin, he produced the tight finite-key bounds vendors now cite, and with Portmann wrote the 2022 Reviews of Modern Physics synthesis. What Snel's law was to classical optics — a measured fact awaiting its theory — accessible-information "security" was to quantum cryptography: Renner supplied the theory.

History

2001

— Canetti formulates Universal Composability for classical cryptographic protocols

2005

— Renner's ETH thesis introduces smooth entropies and the trace-distance QKD criterion

2005

— Devetak and Winter derive the asymptotic secret-key rate I(X;Y) − I(X;E)

2012

— Tomamichel, Lim, Gisin and Renner give the tight finite-key composable analysis

2022

— Portmann and Renner publish the Reviews of Modern Physics synthesis of quantum security

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniv. ed., Ch. 9 & 12 (trace distance, fidelity, quantum information) · Wilde, Quantum Information Theory, 2nd ed., Ch. 9 & 21 (trace distance, min-entropy, hashing) · Watrous, The Theory of Quantum Information, Ch. 3 (trace norm and distinguishability) · Renner, Security of Quantum Key Distribution, PhD thesis, ETH Zurich (2005) · Tomamichel, Lim, Gisin & Renner, Tight finite-key analysis for QKD, Nat. Commun. 3, 634 (2012) · Portmann & Renner, Security in quantum cryptography, Rev. Mod. Phys. 94, 025008 (2022) · Devetak & Winter, Distillation of secret key and entanglement from quantum states, Proc. R. Soc. A 461, 207 (2005) · Preskill, Lecture Notes on Quantum Computation, Ch. 4 (quantum cryptography). The key relations used throughout are: the operational identity $\tfrac12\lVert\rho-\sigma\rVert_1=\max_{0\le P\le\mathbb{1}}\mathrm{Tr}[P(\rho-\sigma)]$ and trace-distance monotonicity under CPTP maps; the Leftover Hashing Lemma and min-entropy definition; the Devetak–Winter rate and the BB84 threshold $1-2h(Q)=0$ at $Q\approx 0.110$ ; and the additive composition theorem. The worked arithmetic is directly checkable: $400-120-58=222$ ; $h(0.05)=0.2864$ so $r=0.427$ ; $h(0.11)\approx\tfrac12$ .

Prerequisites. BB84 Protocol · E91 Protocol · Quantum Bit Error Rate and Sifting · Information Reconciliation and Privacy Amplification · No-Cloning Theorem in Cryptography. Leads to. Information Reconciliation and Privacy Amplification · Photon-Number-Splitting Attack · Six-State and SARG04 Protocols.

Ask the tutor: Ask me to walk through why a patient eavesdropper who waits to measure defeats accessible-information security but not the trace-distance criterion — with the malicious two-state example done explicitly.

What does "composable" actually mean, in one sentence?

It means a key certified once can be dropped into any later cryptographic task and behave like a perfect key, with the overall failure probability rising by no more than the key's parameter $\varepsilon$ . The word comes from composing systems: you build a big protocol from smaller certified pieces, and composability guarantees their parameters simply add rather than interacting catastrophically. Without it, a proof about a key in isolation says nothing about the key in use — the only setting that matters. Trace distance makes the guarantee hold, because it bounds every downstream test at once.

Why trace distance rather than fidelity or mutual information?

Trace distance has three properties that together are composability. First, it equals the maximum distinguishing advantage over all tests (equation 2), so bounding it bounds every adversary. Second, it is monotone under any physical process, so downstream use never increases the distance from ideal — deferral and post-processing cannot help Eve. Third, it obeys the triangle inequality, so stacked sub-protocol errors add. Fidelity lacks the direct distinguishing-advantage reading; accessible information violates monotonicity-under-deferral, the loophole that sinks it. Trace distance is the unique natural quantity with all three.

What is the smooth min-entropy, and why "smooth"?

The plain conditional min-entropy $H_{\min}(X|E)$ measures Eve's best-case guessing power: $2^{-H_{\min}(X|E)}$ is essentially how well she can guess $X$ from $E$ — a worst-case quantity, which security demands. But a strict worst case is brittle: one low-probability bad event can tank it. "Smoothing" optimizes over all states within trace distance $\varepsilon_s$ of the real one, certifying a nearby state's min-entropy and paying $\varepsilon_s$ in the parameter. The result $H_{\min}^{\varepsilon_s}(X|E)$ is robust to rare fluctuations and is exactly what the Leftover Hashing Lemma converts into key.

Why must the classical channel be authenticated?

Because composability is only as strong as its weakest assumption, and an unauthenticated public channel is a gaping hole. If Eve can impersonate Alice to Bob and Bob to Alice, she runs a man-in-the-middle attack: two half-protocols, one with each party, with both sides believing they share a key when in fact each shares a key with Eve — and the quantum part never detects it. Authenticating the channel with an $\varepsilon_{\mathrm{auth}}$ -secure MAC closes the hole, at the cost of a small pre-shared key — which is why QKD is really key expansion, not creation from nothing.

Does the finite-key penalty really matter in practice?

Enormously, in the short-block regime. The asymptotic Devetak–Winter rate assumes infinitely many i.i.d. signals; real systems process finite blocks of $10^6$ to $10^9$ , and the extractable length falls below $n\,r$ by a penalty of order $\sqrt{n}$ from parameter estimation (you must measure the error rate, not know it) and entropy smoothing. For a million-signal block this can erase a large fraction of the naive key — which is why the composable framework makes these penalties explicit rather than hidden in an idealization.

Is a QKD key with

\varepsilon=10^{-9}

ever actually insecure?

Yes, with probability at most $10^{-9}$ — that is the honest, complete statement. Composable security promises not perfection but a key indistinguishable from ideal except with the stated weight. An $\varepsilon=10^{-9}$ key fails to be ideal about once in a billion runs, and when it fails nothing is guaranteed about what leaks. This is far stronger than classical cryptography resting on unproven hardness assumptions, but it is not magic. Choosing $\varepsilon$ is a risk decision: smaller $\varepsilon$ costs key length, so systems pick the largest $\varepsilon$ the application tolerates.