What Does a Secret Key Promise?

1.1 Keys, messages, and adversaries

A security claim is only as strong as the resource it assumes. Before asking what quantum mechanics adds, this section fixes the classical benchmark: what a one-time pad promises, what it costs, and what it leaves unprotected.

1.1.1 Start with the one-time pad

Alice holds a classical message \(M\) and a key \(K\) of the same length, both bit strings. She sends the ciphertext \(C=M\oplus K\), and Bob, who also has \(K\), recovers \(M=C\oplus K\). The scheme is symmetric, deterministic, and costs one key bit per message bit.

Its security claim is conditional on four resources. The key must be uniform, independent of the message, secret from Eve, and used once. Drop any one and the claim fails in a different way: a biased key leaves a statistical trace (Section 1.1.2), reuse leaks relations between messages (Section 1.1.3), and a compromised key is simply known to Eve. QKD produces key material that is close to uniform and independent of Eve even when she controls the channel, but it does not remove the one-time-use requirement.

The pad also has blind spots. It hides content, not length, and it supplies neither integrity nor authentication: anyone can flip ciphertext bits, and the receiver will decrypt a corrupted message. These are separate tasks requiring separate resources. Against an unbounded Eve the guarantee is information-theoretic—no amount of extra computation helps her—whereas a computational cipher assumes Eve cannot solve a specific problem. Before comparing schemes, state the resource each one assumes and the task it actually implements.

1.1.2 Derive perfect secrecy before invoking quantum mechanics

Perfect secrecy says that seeing the ciphertext changes nothing about Eve's beliefs. Formally, for every message \(m\) and ciphertext \(c\) with \(P(C=c)>0\),

The definition compares a posterior with a prior. It says nothing about whether the prior itself is uniform.

Why does a uniform pad satisfy it? Fix \(m\) and \(c\), each of length \(n\). Exactly one key produces that ciphertext from that message, namely \(k=m\oplus c\). Uniformity and independence give

and the right side does not depend on \(m\). Summing over messages gives \(P(C=c)=2^{-n}\), so Bayes' rule returns the prior:

Two features of this calculation are easy to miss. First, the message distribution may be arbitrarily biased: if Eve already believes one message is likely, she still believes that after seeing \(c\), because the ciphertext supplies no new evidence. Second, the key must be uniform relative to Eve. A key that looks random to Alice but is known to Eve is not a key in this sense.

A biased key shows the failure concretely. Take a one-bit message, a uniform message prior, and \(P(K=0)=0.9\). Then \(P(C=0\mid M=0)=0.9\) while \(P(C=0\mid M=1)=0.1\). Observing \(C=0\) raises the posterior for \(M=0\) from \(1/2\) to

Secrecy also costs key length. Fix a ciphertext \(c\). Correct decryption assigns at most one message to each key, so at most \(|K|\) messages can be recovered from \(c\). Perfect secrecy, for a prior that gives every message positive probability, requires every message to remain possible given \(c\), so all \(|M|\) messages must be recoverable. Hence \(|K|\ge|M|\). QKD does not repeal this accounting; it supplies the shared randomness that encryption later consumes.

1.1.3 A public channel can be private without being authentic

Perfect secrecy is a statement about a single use. Reuse the same pad for two messages and the key cancels:

Eve now holds a relation between the plaintexts. If she can guess one message, even partially, she recovers the corresponding part of the other. The one-time condition is not bureaucratic; it is what prevents this cancellation.

Confidentiality and integrity fail for different reasons, so repairing one does not repair the other. An attacker who cannot read \(C\) can still replace it with \(C\oplus\Delta\), and decryption then yields \(M\oplus\Delta\). Bob cannot notice unless the message or the channel supplies authentication. A one-time pad used correctly therefore guarantees confidentiality and nothing else.

It helps to draw the QKD setting as two channels with different powers for Eve.

If the classical channel were public but unauthenticated, Eve could sit between Alice and Bob, run one exchange with each, and relay messages. Both parties would see ordinary quantum statistics while each final key was shared with Eve rather than with each other. This is why QKD consumes an initial short secret to authenticate, and why that cost must be budgeted rather than assumed away.

A key is therefore defined by a joint state, not by a list of bits that look random. Section 1.2 shows what quantum mechanics restricts, and Section 1.3 makes the joint-state comparison precise.

1.2 Quantum states and copying

Quantum mechanics enters the argument twice: it restricts what Eve can copy, and it forces a detectable price when she obtains information. This section develops both statements one qubit at a time and marks clearly where a security proof is still missing.

1.2.1 Use an inner-product test

Fix the two bases used throughout the course. The Z basis is \(\{|0\rangle,|1\rangle\}\); the X basis is \(\{|+\rangle,|-\rangle\}\), where

The bases are incompatible: a Z eigenstate measured in X gives each outcome with probability \(1/2\), and vice versa. That fact is the resource the protocol will exploit.

Suppose a unitary \(U\) copied two states perfectly into a fixed blank register \(|b\rangle\):

Take inner products of the two equations and use that \(U\) preserves inner products:

Writing \(s=\langle\psi|\phi\rangle\), the condition \(s=s^2\) forces \(s=0\) or \(s=1\). Two distinct nonorthogonal states cannot both be copied by the same machine. Orthogonal states can: a controlled-NOT with the state as control and a blank \(|0\rangle\) as target copies \(|0\rangle\) and \(|1\rangle\) exactly.

This is a real restriction, but it is not a protocol security proof. Eve need not copy. She can interact weakly with many signals, keep a quantum memory, exploit channel loss, or coordinate a collective attack, and she may accept a nonzero chance that the protocol aborts. No-cloning rules out one strategy; security must bound every strategy the physical model allows.

1.2.2 Build the density matrices Eve must distinguish

A classical label and the quantum signal carrying it are different objects, and it pays to keep them apart. If Alice sends the X-basis bit \(+\), the state held by Bob or Eve is

These are \(|+\rangle\langle+|\) and \(|-\rangle\langle-|\) written in the Z basis. The diagonal entries are the Z-measurement probabilities; the off-diagonal entries are the coherences that an X measurement reads.

Now average over the bit. A uniform mixture cancels the off-diagonal entries:

and the same is true of \((|0\rangle\langle0|+|1\rangle\langle1|)/2\). If the bit is uniform and nothing else leaks the basis, the state Eve holds is \(I/2\) whichever basis Alice used. No measurement can tell the two cases apart, because the two descriptions are literally the same operator. This is an identity about states, not a statement about Eve's ignorance of the notation.

Before the basis is announced, Eve faces a different question: she may know that the bit is uniform but not which basis was used. The two candidate states are

The first averages the Z and X preparations of bit \(0\), the second the preparations of bit \(1\), each weighted equally because Eve does not know the basis. Their difference is \((X+Z)/2\), whose eigenvalues are \(\pm1/\sqrt2\). The optimal binary discrimination probability is given by the Helstrom formula

where the trace norm is the sum of the singular values. For this pair the trace norm is \(2/\sqrt2=\sqrt2\), so \(p_{\rm guess}=(1+1/\sqrt2)/2\approx0.8536\). Eve can beat a coin flip by a wide margin if she is willing to consume the signal in that measurement.

That number is not yet a successful attack. Eve must hand Bob a signal, and Alice later announces the basis, so Eve's guess is judged on the whole transcript rather than on one measurement. The calculation measures how much the two bit hypotheses overlap; it does not say how much information survives the rest of the protocol.

1.2.3 Disturbance comes from correlations with a memory

Eve need not guess at all. She can let a unitary entangle each signal with an ancilla she keeps, so that her record is correlated with the bit while the signal continues to Bob. The price of that correlation is the subject of this subsection.

Consider an attack that leaves the Z basis untouched but writes the value into Eve's ancilla:

Linearity fixes the action on superpositions. For \(|+\rangle\) the joint state becomes

Tracing out Eve leaves Bob with the reduced state

The off-diagonal coherence has been multiplied by the overlap \(\langle e_1|e_0\rangle\). Bob's X-basis error probability is the probability of the \(|-\rangle\) outcome,

The two extremes are instructive. If \(e_0=e_1\), the overlap is one, Eve's record is the same for both bits, and Bob sees no error. If \(\langle e_1|e_0\rangle=0\), Eve can read the Z bit perfectly, and Bob's X outcome is uniformly random. Partial overlap interpolates between the two: information and disturbance trade off quantitatively.

This is the mechanism behind the slogan that measurement disturbs a state. Nothing reaches in and "kicks" the qubit. Eve's ancilla becomes correlated with the signal, the correlations are inaccessible to Bob, and the interference he would need to see disappears. It also explains why testing only Z is inadequate: this attack produces no Z errors at all while Eve holds a perfect record. BB84 tests complementary preparations precisely to expose the missing coherence, which is the subject of Section 2.2.

1.3 Authentication and composability

Secrecy needs a definition that survives composition with other protocols. This section states the definition, gives it an operational meaning, and tests it on an example where intuition alone would mislead.

1.3.1 Define the ideal output

A key protocol makes three separate promises, and each needs its own error parameter. Correctness bounds the probability that Alice and Bob accept while holding different keys. Secrecy says the key they hold is indistinguishable from a uniform key independent of Eve. Authentication bounds the chance that Eve can impersonate a party on the classical channel.

These are separate on purpose. A protocol can be correct and secret but forgeable, or authenticated and secret but occasionally wrong. Availability is separate again: Eve can always block signals and prevent a key from being produced. A secrecy theorem for accepted runs does not contradict that; it says nothing about runs that abort.

Authentication deserves emphasis because it is the resource QKD cannot manufacture from nothing. An authenticated classical channel lets Eve listen and delay but not undetectably alter messages. Without it, she can run one exchange with Alice and another with Bob, as described in Section 1.1.3. In practice authentication uses a short pre-shared secret and a universal hash family: the tag gives a bounded forgery probability per message, and the key cost must be budgeted explicitly.

1.3.2 Write the real and ideal key states

To compare a real protocol with an ideal one, put both in the same mathematical form. Let \(K\) be the \(\ell\)-bit classical output and let \(E\) denote everything Eve holds: her quantum memory, her classical records, and the public transcript. The joint state is classical on Alice and Bob's side and quantum on Eve's:

The ideal state is a uniform key independent of Eve:

The distance between the two is measured by the trace distance

where the trace norm is the sum of the singular values. For states diagonal in the same basis this is exactly the classical total variation distance, \(T=\frac12\sum_x|p_x-q_x|\). The quantum definition has the operational meaning we need: substituting one state for the other changes the probability of any subsequent event by at most \(T\). Equivalently, an optimal test distinguishing the two with equal prior succeeds with probability \(\frac12+\frac{T}{2}\).

Protocols can abort, so the comparison is made on accepted runs and weighted by the probability of accepting:

The weighting matters. Conditioning on a rare acceptance event can make the conditional state far from ideal, while the unconditional claim remains meaningful because that event is unlikely. If acceptance never occurs, the left side is interpreted as zero. Correctness is bounded separately by \(P[K_A\ne K_B\ \text{and pass}]\le\epsilon_{\rm cor}\).

If the output length is announced after the fact, the ideal state must be uniform for each announced length. The examples in this course fix the length in advance, which keeps the accounting simple.

1.3.3 Test secrecy with an explicit counterexample

Suppose Alice and Bob share a uniform bit and Eve has a perfect copy. Correctness is perfect, and each honest party sees zeros exactly half the time, so a histogram of \(K\) alone looks ideal. The joint distribution tells a different story.

Here \(E\) is classical, so the trace distance reduces to half the sum of the absolute differences:

The operational difference is easy to see. Ask whether \(K=E\). In the real protocol the answer is always yes; in the ideal protocol it is yes with probability \(1/2\). A test that looks only at the key's histogram cannot detect the leak, but a test that looks at the key together with Eve's information can.

The distance also composes. Any later processing—hashing, encryption, an adversary's measurement—cannot increase trace distance, so replacing the real key by an ideal key inside a larger protocol changes its output by at most the secrecy error. Applying several such replacements in sequence adds their errors by the triangle inequality. That is what makes a small \(\epsilon_{\rm sec}\) a usable guarantee rather than a decorative number.

One interpretation of \(\epsilon_{\rm sec}\) should be avoided. It does not mean that Eve knows the entire key with probability \(\epsilon\), or that she knows nothing otherwise. It means the real joint state is close to one in which she knows nothing, and the distance bounds what any distinguisher can notice.

Authentication fits the same replacement argument. A universal-hash tag with a secret hash choice gives a bounded forgery probability per message, but the hash key is consumed, and reusing it degrades the bound. We will budget authentication bits explicitly rather than treat the public channel as free.

The chapter's three ideas now connect: a key is a resource with a precise cost (1.1); quantum mechanics constrains how Eve can acquire it and makes her acquisition visible (1.2); and composable security compares the whole joint state, transcript included, with an ideal key (1.3). Chapter 2 turns these ingredients into the BB84 protocol.