Starting point: POVMs, trace distance and the Helstrom bound, no-cloning, Holevo-type states and channel rates; security definitions and classical processing are introduced in context.
Keep in view: Use a prepare-and-measure key-distribution protocol to identify the information an eavesdropper might obtain.
We have found the rates at which a channel can deliver classical and quantum messages reliably. Along the way, two constraints kept appearing. No device copies an unknown state, and any measurement that extracts information from nonorthogonal states disturbs them.
Reliable delivery is not secret delivery. A classical signal can be copied by anyone who taps the line, and nobody notices. Can the two quantum constraints turn into a guarantee that an eavesdropper learned nothing? Classically, a message is perfectly hidden if it is combined with a random key as long as itself, so the real problem is sharing such a key. We build a key-distribution protocol from nonorthogonal signals and see why it uses two bases. Turning its raw data into a key requires estimating errors, correcting them in public, and shortening the result to remove what leaked. A simple attack shows how eavesdropping reveals itself. Finally we state what "secure" must mean and which assumptions a proof needs.
16.1 Key Distribution
Alice and Bob want a shared random key that an eavesdropper, Eve, cannot predict. If Alice XORs her message with a uniformly random key of the same length, the result is itself uniformly random and reveals nothing about the message; this is the one-time pad. So how can they share the key? We first build a protocol from four qubit states in two bases and see what the second basis is for. Then we redescribe it with Bell pairs, which shows what Eve's ignorance means.
A first idea is for Alice to send random bits as \(\ket0\) and \(\ket1\). What stops Eve? Nothing. These states are orthogonal, so Eve can measure Z, record the bit and resend a perfect copy. Bob sees no change. The fix is to send states that no one can copy without disturbing them.
In the protocol known as BB84, after Bennett and Brassard who proposed it in 1984, Alice chooses a random bit and, independently, a random basis, Z or X. She sends \(\ket0\) or \(\ket1\) in the Z basis, and \(\ket+\) or \(\ket-\) in the X basis. The four states include nonorthogonal pairs, so no-cloning forbids a perfect copier. Bob measures each qubit in a basis he chooses at random.
Afterwards they announce their bases, not their bits, over a public channel and keep only the rounds where the bases matched. This step is called sifting. The public channel must be authenticated: Eve may read every message, but she cannot alter one or pretend to be Alice or Bob. Classical authentication schemes need a short shared secret to begin with, so the protocol expands a key rather than creating one from nothing.
What does Bob see? On a matching round, an undisturbed signal gives him Alice's bit with certainty. On a mismatched round he gets a fair bit; for example, \(\ket0\) measured in X gives plus or minus with probability \(1/2\) each. With fair basis choices, half the rounds match, so 1,000 signals leave about 500 sifted bits, with fluctuations. The bit, Alice's basis, Bob's basis and his outcome are four different variables, and only the bases are made public.
The sifted string is raw material, not yet a secret key. It may contain errors, and Eve may know part of it. Testing, correcting and shortening it will cost some of its length.
Is there a way to see why matching rounds should be secret? Redescribe the protocol. Alice prepares a Bell pair, sends one half to Bob, and measures her own half in Z or X. Since \(\ket{\Phi^+}=(\ket{00}+\ket{11})/\sqrt2=(\ket{++}+\ket{--})/\sqrt2\), her outcome leaves Bob's qubit in the matching state of the same basis. From Bob's side this is exactly BB84, with Alice's bit chosen by her measurement instead of a coin.
In this picture secrecy has a clean meaning. Suppose Alice and Bob could confirm that they really share the pure state \(\ket{\Phi^+}\). Any eavesdropper's system \(E\) would then have to be part of a larger pure state whose \(AB\) part is already pure. That is possible only if the whole state is a product, \(\ket{\Phi^+}_{AB}\otimes\ket e_E\). So Eve would be uncorrelated with their results. Testing the error rate is, in effect, testing how close they are to sharing Bell pairs.
The redescription is a tool for proofs. It does not remove assumptions about the real devices: an actual prepare-and-measure system must satisfy the conditions used in its proof.
An ideal BB84 signal: Alice selects bit x and basis a; Bob selects basis b. The wire between preparation and readout is the transmitted quantum system. Keep rounds with a=b.
Problems
Problem 16.1. If the basis choices are independent and fair, what fraction of rounds are sifted, and what is the undisturbed error rate among those rounds?
Worked solution
The two matching choices, ZZ and XX, have probability 1/4 each, so half the rounds survive on average. In the ideal undisturbed model those rounds have zero bit error. This is not yet a final secret-key rate.
16.2 From Data to a Key
The sifted strings of Alice and Bob may disagree in places, and Eve may know some of their bits. How do they turn them into identical strings that Eve knows nothing about? They first estimate the error rate from a public sample. Then they correct the remaining errors by public discussion, which leaks information. Finally they shorten the corrected string so that the leaked information, and anything Eve learned on the line, no longer says anything about the result.
How can Alice and Bob tell how noisy their strings are without revealing them? They choose a random subset of sifted rounds and publish those bits. The fraction of disagreements in the subset estimates the quantum bit error rate \(Q\), the fraction of sifted bits on which Alice and Bob differ. The published bits are then discarded from the key.
A finite sample only bounds the error rate of the unpublished bits, with a stated probability that the bound fails. Seeing no errors in a small sample does not prove that the channel is noiseless or that nobody listened.
The remaining errors are corrected by reconciliation. For example, Alice announces the parities of blocks of her string, and Bob flips bits until his parities match. Each published parity tells Eve something. The security account must therefore subtract everything revealed during reconciliation.
How much does publishing a parity cost, and how do Alice and Bob pay for it? Take a two-bit key, equally likely to be 00, 01, 10 or 11. Eve starts with 2 bits of uncertainty. After the parity is published, only two strings remain: 00 or 11 if the parity is 0, and 01 or 10 if it is 1. Her uncertainty has dropped to 1 bit. Keeping both bits and calling them secret would ignore the public message.
Yet one bit is still perfectly secret. Given either parity, the first bit is still 0 or 1 with equal probability: 00 and 11 differ in it, and so do 01 and 10. So Alice and Bob keep the first bit and discard the second. Shortening the string by the amount that leaked restores secrecy.
For long strings, and for leaks that are not simple parities, the shortening is done with a hash function, a map from long strings to shorter ones. It is chosen at random from a suitable family and announced publicly. A family that turns any string about which Eve is sufficiently uncertain into a nearly uniform, nearly independent output is called a randomness extractor. We quote the leftover hash lemma, extended by Renner to adversaries holding quantum systems: the output can be about as long as Eve's remaining uncertainty, suitably measured, minus a safety margin. This step is privacy amplification.
The hash seed may be public, but it must meet the assumptions of the theorem used, and an arbitrary short checksum does not. Hashing a string that Eve already knows cannot make it secret. Privacy amplification needs uncertainty that remains against Eve's actual information, including any quantum memory she keeps. The parity example explains the mechanism; the quantum bound requires the cited theorem.
Problems
Problem 16.2. Can Alice and Bob keep the publicly revealed test bits as secret key?
Worked solution
No. Those bit values are public. They estimate channel statistics and must be excluded from the secret output.
16.3 Security Assumptions
The protocol rests on the claim that listening causes errors. How many errors does a simple attack cause, and what must a security proof show beyond that? We compute the error rate of an attack that measures and resends every signal. Then we state the criterion that a final key must meet to be called secure, and quote the ideal key rate together with the assumptions behind it.
Suppose Eve intercepts every signal, measures it in Z or X at random, and resends the state she found. What error rate does Bob see on sifted rounds?
Take a sifted Z round on which Alice sent \(\ket0\). If Eve chose Z, she finds 0, resends \(\ket0\), and causes no error. If she chose X, she resends plus or minus, and Bob's Z result is fair. Averaging her equally likely choices gives
By symmetry the same holds for every sifted round. This attack is easy to detect. It is also only one strategy. A general attack can interact with many signals jointly and keep its systems in a quantum memory until all public messages are known. A security proof must cover every attack in the declared class.
Authentication is essential. Without it, Eve can pose as Bob to Alice and as Alice to Bob, run the protocol with each, and read everything. No quantum effect prevents that.
What should "the key is secret" mean? Let \(K\) be the final key and \(E\) everything Eve holds, and let \(\rho_{KE}\) be their joint state, in the form used for the Holevo bound: a classical key value paired with Eve's quantum state. The ideal is a uniform key \(\tau_K\), every string equally likely, independent of Eve, which is \(\tau_K\otimes\rho_E\). We ask the real state to be close to the ideal in trace distance:
Why trace distance? By the Helstrom bound, no test of any kind can tell the real situation from the ideal with success better than \((1+\epsilon_{\rm sec})/2\). So the key can be used anywhere an ideal key could, and the failure probability is at most \(\epsilon_{\rm sec}\). A criterion with this property is called composable. A separate parameter bounds the probability that Alice's and Bob's keys differ, and the formal definition also accounts for runs that abort.
How long can the key be? We quote the result of Shor and Preskill (2000). For ideal single-photon BB84, with many rounds, symmetric basis choices and one-way classical processing, the secret key per sifted bit can approach
\[r=1-2h_2(Q)\]
whenever this is positive. One \(h_2(Q)\) pays for error correction and the other for what Eve may have learned. At \(Q=0.05\), \(h_2(Q)\approx0.2864\) and \(r\approx0.4272\). The rate reaches zero near \(Q\approx0.11\). At the intercept-resend value \(Q=1/4\) it is negative, so no key can be extracted.
This formula is an ideal asymptotic bound, not a finite-device key rate. Real security must account for the source, the detectors, loss, authentication, finite statistics and everything leaked during processing. A demonstration of the protocol does not certify a secure implementation.
Every claim in the course, from Bob's guess about a card to a secret-key rate, has needed the same preparation: the task, the allowed resources, the assumptions and the error criterion, all stated before asking what is possible.
Problem 16.3. Why is secrecy alone insufficient if Alice’s and Bob’s keys differ?
Worked solution
A key must also be correct for its intended use. Composable definitions separately control disagreement and deviation from uniform independence, with a stated total failure budget.
Transfer problem. In the ideal intercept-resend model, Eve attacks a fraction f of signals independently. Find the expected sifted error rate. Can the same observed error determine f for an arbitrary attack?
Worked solution
An attacked sifted round has error 1/4; unattacked ideal rounds have zero error. Thus the model predicts Q=f/4, for example Q=0.05 when f=0.2. This inference uses the particular independent intercept-resend model. General attacks and device noise can produce the same observed error, so Q does not identify a unique adversary strategy.
Summary
Quantum key distribution protocols such as BB84 and E91 leverage non-orthogonal states or entanglement monogamy so any eavesdropping attempt by Eve introduces detectable disturbance in parameter estimation.
Converting raw sifted detections into a secure key requires classical information reconciliation (error correction) followed by privacy amplification using universal hash functions.
Finite-key composable security bounds the trace distance between the final shared key and an ideal uniform key that is completely decoupled from Eve’s quantum side information \(E\).
Questions and worked problems
These exercises draw on the whole chapter. Attempt each question before opening a hint, explain your reasoning, then compare it with the worked solution.
In BB84, Alice and Bob each choose the \(Z\) basis with probability \(0.9\) and the \(X\) basis with probability \(0.1\), independently. What fraction of rounds is sifted? Why might they prefer this to fair basis choices, and what must they still be able to do with the rarely used basis?
Hint 1
Matching probability is \(0.9^2+0.1^2\).
Hint 2
Security relies on testing both bases.
Worked solution
Matching occurs with probability \(0.81+0.01=0.82\), compared with \(0.5\) for fair choices, so far fewer rounds are discarded. The \(X\) rounds are still essential: they are where an attack that measures in \(Z\) shows up as errors. With biased choices, Alice and Bob need enough \(X\)-basis data to estimate its error rate with the required confidence, which the analysis must account for.
Evaluate the ideal asymptotic key rate \(1-2h_2(Q)\) per sifted bit for \(Q=0.02\) and \(Q=0.11\). What does the second value suggest about the tolerable error rate in this model?
Hint 1
\(h_2(0.02)\approx0.141\).
Hint 2
\(h_2(0.11)\approx0.500\).
Worked solution
At \(Q=0.02\): \(1-2(0.141)\approx0.717\) secret bits per sifted bit. At \(Q=0.11\): \(1-2(0.500)\approx0\). In this ideal one-way model, no key can be extracted once the error rate reaches about \(11\%\). Finite data, detector imperfections, and authentication costs reduce the usable rate and the tolerable error further.
A sifted raw key of \(6\) uniformly random bits is reconciled by publishing the parities of the pairs \((1,2)\), \((3,4)\), and \((5,6)\). How many bits of uncertainty does Eve have left, assuming she knew nothing else? How long a secret key can be extracted?
Hint 1
Each published parity removes one bit of uncertainty.
Hint 2
Choose one bit from each pair.
Worked solution
Each independent parity halves the possible strings, so Eve’s uncertainty falls from \(6\) bits to \(3\). Taking the first bit of each pair gives \(3\) bits that are uniform and independent of the published parities, so a \(3\)-bit key can be extracted. Every bit leaked in public reconciliation must be subtracted from the final key length.
Eve intercepts every signal, always measures in \(Z\), and resends her result. (a) Find the error rate on sifted \(Z\) rounds and on sifted \(X\) rounds. (b) What is the average sifted error rate with fair basis choices? (c) How can Alice and Bob detect this attack more effectively than by the average alone, and how much does Eve learn?
Hint 1
In \(Z\) rounds Eve’s measurement does not disturb the state.
Hint 2
In \(X\) rounds Bob receives a \(Z\) eigenstate and measures \(X\).
Worked solution
(a) On \(Z\) rounds Eve measures the right basis, resends the same state, and causes no error. On \(X\) rounds she resends \(\ket0\) or \(\ket1\), and Bob’s \(X\) measurement is a fair coin: error \(\frac12\). (b) The average is \(\frac14\), the same as the random-basis attack. (c) Estimating the error separately for each basis shows \(0\) in \(Z\) and \(\frac12\) in \(X\), a clear signature. Eve learns every \(Z\) key bit and nothing about \(X\) key bits. Basis-resolved error estimates constrain attacks more tightly than a single average.
In an intercept-resend attack, Eve measures every signal in the intermediate basis \(\ket{b_0}=\cos\frac\pi8\ket0+\sin\frac\pi8\ket1\), \(\ket{b_1}=-\sin\frac\pi8\ket0+\cos\frac\pi8\ket1\), guessing bit \(0\) on \(b_0\), and resends the state she found. (a) For Alice’s \(\ket0\), find the probability that Eve guesses correctly and the error Bob sees in a \(Z\) measurement. (b) Compare with the random \(Z\)/\(X\) intercept-resend attack. (c) What does the comparison show?
Bob errs if Eve resends \(\ket{b_0}\) and he finds \(1\), or \(\ket{b_1}\) and he finds \(0\).
Worked solution
(a) Eve guesses correctly with probability \(\cos^2\frac\pi8\approx0.854\). Bob’s error is \(\cos^2\frac\pi8\sin^2\frac\pi8+\sin^2\frac\pi8\cos^2\frac\pi8=2(0.854)(0.146)=0.25\). The basis is equally inclined to \(Z\) and \(X\), so \(X\) rounds behave the same way. (b) The random-basis attack also causes \(25\%\) error, but Eve then guesses correctly only \(\frac12\cdot1+\frac12\cdot\frac12=75\%\) of the time. (c) For the same disturbance, a cleverer measurement gives Eve more information. Security proofs must bound what any attack can learn for a given error, not analyse one convenient attack.
Alice and Bob test \(n=100\) randomly chosen sifted bits and find no errors. (a) If the true error rate is \(Q\), what is the probability of seeing no errors? (b) What is the largest \(Q\) that remains consistent with this observation if they accept a failure probability of \(10^{-3}\)? (c) What must the security analysis use in place of “\(Q=0\)”?
Hint 1
\(P(\text{no errors})=(1-Q)^n\).
Hint 2
Solve \((1-Q)^{100}=10^{-3}\).
Worked solution
(a) \((1-Q)^{100}\). (b) Setting \((1-Q)^{100}=10^{-3}\) gives \(Q=1-10^{-0.03}\approx0.067\). Any error rate up to about \(6.7\%\) could produce zero observed errors with probability at least \(10^{-3}\). (c) The analysis must use this upper bound (or a sharper one), together with its failure probability, as the error parameter. With \(Q\approx6.7\%\), the ideal key rate is \(1-2h_2(0.067)\approx0.29\) instead of \(1\). Finite data costs key length even when nothing goes wrong.
A raw key \(x_1x_2x_3x_4\) is uniformly random, and Eve has learned only the parity \(x_1\oplus x_2\). (a) Show that \(x_1\) is uniform and independent of Eve’s information. (b) Give a \(3\)-bit key that is perfectly secret, and explain why \((x_1,x_2,x_3)\) would not be. (c) How does this illustrate privacy amplification?
Hint 1
For each value of the parity, \(x_1\) is still \(0\) or \(1\) with equal probability.
Hint 2
\(x_2=x_1\oplus(x_1\oplus x_2)\).
Worked solution
(a) For either value of \(x_1\oplus x_2\), there are two equally likely pairs, one with \(x_1=0\) and one with \(x_1=1\), so \(x_1\) is uniform and independent of the parity. (b) \((x_1,x_3,x_4)\) is uniform and independent of what Eve knows, so it is perfectly secret. \((x_1,x_2,x_3)\) is not: Eve can compute \(x_1\oplus x_2\) from it, so only \(8/2=4\) of its \(8\) values are possible given her knowledge. (c) Privacy amplification maps the raw key to a shorter string chosen to be independent of the adversary’s information; when Eve knows \(k\) independent parities of an \(n\)-bit uniform key, \(n-k\) secret bits can be extracted. Quantum security proofs supply the corresponding bound when Eve holds quantum information.
A student claims: “BB84 is secured by physics, so Alice and Bob do not need an authenticated classical channel.” Describe an attack by an adversary who controls both the quantum channel and an unauthenticated classical channel, and explain what authentication provides.
Hint 1
Can Eve pretend to be Bob to Alice and Alice to Bob?
Hint 2
No-cloning protects the quantum signals only against an outsider.
Worked solution
Eve runs one BB84 session with Alice, pretending to be Bob, and another with Bob, pretending to be Alice, using the unauthenticated channel to answer each party’s basis announcements and tests. Each session shows no disturbance, because Eve is a legitimate endpoint in each. She ends up with one key shared with Alice and another with Bob, and can read and re-encrypt every message. The quantum part guarantees only that an outsider cannot learn a key without causing errors; authentication guarantees that the outsider is not the other endpoint. It requires a short pre-shared secret, so QKD expands a shared key rather than creating one from nothing.
In the entanglement-based description, suppose Eve copies the \(Z\) value of the photon in transit with a CNOT onto her own qubit, so that Alice, Bob, and Eve share \((\ket{000}+\ket{111})/\sqrt2\). (a) What error rate do Alice and Bob see in \(Z\) rounds, and what does Eve know? (b) Compute \(\langle X_AX_B\rangle\) for this state, and the error rate in \(X\) rounds. (c) What principle does the result illustrate?
Hint 1
\(X_A X_B\) maps \(\ket{000}\) to \(\ket{110}\).
Hint 2
An \(X\)-round error means Alice’s and Bob’s \(\pm\) results differ.
Worked solution
(a) In \(Z\) rounds the three outcomes always agree: no error, and Eve knows every \(Z\) bit. (b) \(X_AX_B\ket{000}=\ket{110}\) and \(X_AX_B\ket{111}=\ket{001}\), both orthogonal to the state, so \(\langle X_AX_B\rangle=0\). Alice’s and Bob’s \(X\) outcomes are uncorrelated, giving error \(\frac12\) in \(X\) rounds. (c) Complementarity: Eve’s perfect knowledge of \(Z\) forces Alice’s and Bob’s \(X\) correlation to vanish. Low error in one basis together with low error in the complementary basis is what limits an eavesdropper, which is why BB84 tests both.
The six-state protocol uses the \(Z\), \(X\), and \(Y\) bases, with eigenstates \(\ket0,\ket1\), \(\ket\pm\), and \((\ket0\pm i\ket1)/\sqrt2\), chosen with equal probability by Alice and Bob. (a) What fraction of rounds is sifted? (b) In an intercept-resend attack where Eve picks one of the three bases at random, what sifted error rate results? (c) Compare with BB84’s \(\frac14\), and explain the trade-off.
Hint 1
Eve picks the wrong basis with probability \(\frac23\).
Hint 2
A wrong-basis resend gives Bob a fair result in his basis.
Worked solution
(a) Bases match with probability \(\frac13\). (b) Eve chooses the right basis with probability \(\frac13\) (no error) and a wrong one with probability \(\frac23\), after which Bob’s result is a fair coin, so the error is \(\frac23\cdot\frac12=\frac13\). (c) The attack causes \(33\%\) error instead of \(25\%\), so it is easier to detect and the protocol tolerates somewhat more noise. The price is a lower sifting rate, \(\frac13\) instead of \(\frac12\), and a third basis to implement. Using more mutually unbiased bases makes eavesdropping more conspicuous at the cost of efficiency.
