The BB84 Protocol

BB84 is a quantum key distribution protocol: a procedure by which two parties, conventionally Alice and Bob, establish a shared random secret key whose secrecy is guaranteed by physics rather than by computational hardness assumptions. The core mechanism is conjugate coding: each classical bit is encoded into a qubit using one of two mutually unbiased bases, chosen independently and uniformly at random for every qubit. The two bases used in the original protocol are the rectilinear basis $\{|0\rangle, |1\rangle\}$ and the diagonal basis $\{|+\rangle, |-\rangle\}$, where

These two bases are mutually unbiased: a state prepared in one basis, when measured in the other, yields a uniformly random outcome, giving no information about the original bit. This is the operational content of complementarity for BB84, and it is what makes eavesdropping detectable — an eavesdropper who does not know the preparation basis cannot measure without a significant chance of disturbing the state, by the The No-Cloning Theorem Revisited and the disturbance principle of quantum measurement. The protocol proceeds in two conceptually distinct phases. In the quantum phase, Alice sends a stream of qubits, each randomly encoding a bit in a randomly chosen basis; Bob measures each in a randomly chosen basis of his own. In the classical post-processing phase, Alice and Bob use an authenticated (but not necessarily secret) classical channel to compare basis choices, discard mismatched measurements ("sifting"), estimate the error rate on a sample, and — if the error rate is low enough to prove security — run error correction and privacy amplification to distill a shorter, provably secure final key.

The protocol has five stages. We walk through each precisely, then give pseudocode covering the entire pipeline.

1. Quantum state preparation and transmission (Alice). For each of $N$ rounds, Alice picks two independent uniformly random bits: $a_i \in \{0,1\}$ (the raw key bit) and $b_i \in \{0,1\}$ (the basis choice, $0$ = rectilinear, $1$ = diagonal). She prepares the qubit:

• $b_i = 0, a_i = 0 \to |0\rangle$
• $b_i = 0, a_i = 1 \to |1\rangle$
• $b_i = 1, a_i = 0 \to |+\rangle$
• $b_i = 1, a_i = 1 \to |-\rangle$

and sends it to Bob over a quantum channel (fiber, free-space link, or satellite downlink).

2. Measurement (Bob). For each incoming qubit, Bob independently picks a random basis $b_i' \in \{0,1\}$ and measures. If $b_i' = b_i$ (he guessed Alice's basis correctly), his outcome $a_i'$ equals $a_i$ with certainty in the noiseless case. If $b_i' \neq b_i$, his outcome is uniformly random and uncorrelated with $a_i$.

3. Basis reconciliation / sifting. Over the public classical channel, Alice and Bob announce their basis choices $b_i, b_i'$ (never the bit values). They keep only the rounds where $b_i = b_i'$; this subset is the sifted key. On average, half the rounds survive sifting, since the two basis choices agree with probability $1/2$ independently at each round.

4. Error estimation (parameter estimation). Alice and Bob publicly reveal a random subset of the sifted key (say, of size $m$) and compare values directly. The fraction of disagreements is the quantum bit error rate (QBER), $Q$. In an idealized noiseless channel with no eavesdropper, $Q = 0$. Any eavesdropping strategy that extracts information necessarily introduces disturbance, raising $Q$ above zero. If $Q$ exceeds a threshold determined by the security proof (roughly $11\%$ for the BB84 protocol under the strongest known attacks, and lower in practical implementations with finite-key effects), Alice and Bob abort — the channel is deemed compromised or too noisy to guarantee security.

5. Error correction and privacy amplification. If $Q$ is below threshold, Alice and Bob run classical information reconciliation (e.g., a Cascade or LDPC-based protocol) over the authenticated public channel to correct the remaining discrepancies in the unrevealed sifted bits, producing an identical string on both sides. They then apply privacy amplification — hashing the reconciled string down with a randomly chosen universal hash function — to compress out the bits an eavesdropper might partially know, yielding a shorter final key about which Eve's information is exponentially small. ``` BB84_PROTOCOL(N, error_threshold): // ---------- Quantum phase ---------- for i = 1 to N: a[i] = random_bit() // Alice's raw bit b[i] = random_bit() // Alice's basis: 0=rectilinear, 1=diagonal qubit = PREPARE(a[i], b[i]) // encode bit in chosen basis SEND_OVER_QUANTUM_CHANNEL(qubit) b_prime[i] = random_bit() // Bob's basis guess received = RECEIVE_FROM_QUANTUM_CHANNEL() a_prime[i] = MEASURE(received, b_prime[i]) // ---------- Classical post-processing ---------- // Step 1: Sifting sifted_indices = { i : PUBLIC_ANNOUNCE(b[i]) == PUBLIC_ANNOUNCE(b_prime[i]) } sifted_key_A = { a[i] : i in sifted_indices } sifted_key_B = { a_prime[i] : i in sifted_indices } // Step 2: Error estimation on a random public sample sample = RANDOM_SUBSET(sifted_indices, size = m) mismatches = COUNT(a[i] != a_prime[i] for i in sample) Q = mismatches / m remove sample from sifted_key_A, sifted_key_B // never reuse revealed bits if Q > error_threshold: ABORT("channel insecure or too noisy") // Step 3: Error correction (reconciliation) (corrected_A, corrected_B, leaked_bits) = RECONCILE(sifted_key_A, sifted_key_B) // e.g. Cascade protocol assert corrected_A == corrected_B // Step 4: Privacy amplification key_length = ESTIMATE_SECURE_LENGTH(len(corrected_A), Q, leaked_bits) hash_fn = CHOOSE_RANDOM_UNIVERSAL_HASH(key_length) final_key = hash_fn(corrected_A) return final_key ``` The figure below shows the pipeline end to end, including where information is discarded at each stage.

Communication and computational complexity. Preparing and sending $N$ qubits costs $O(N)$ quantum channel uses. Sifting, error sampling, and basis announcement each cost $O(N)$ classical bits of communication and $O(N)$ time for both parties, since every round is processed independently in constant time. Reconciliation protocols such as Cascade run in $O(N \log N)$ classical bit exchanges in typical implementations, dominated by iterative parity-check rounds. Privacy amplification via universal hashing takes $O(N)$ time to evaluate a hash from a suitable family (e.g., Toeplitz-matrix hashing), and the output key length is $O(N)$ but strictly smaller than the sifted key length. Overall the protocol is linear in the number of transmitted qubits, which is efficient — the overhead relative to naively wanting $N/2$ perfectly secret bits is a constant factor plus the cost of error correction and amplification, both of which scale linearly with mild logarithmic reconciliation overhead.

Sifting yield. Since Alice's and Bob's basis choices are independent fair coins, $\Pr[b_i = b_i'] = 1/2$, so the expected sifted key length is $N/2$, with fluctuations of order $O(\sqrt{N})$ by the law of large numbers (a Chernoff bound gives exponentially small deviation probability for any fixed relative error).

Correctness in the absence of noise or eavesdropping. When $b_i = b_i'$, Bob measures in the same basis Alice used to prepare the state, and quantum measurement in the preparation basis returns the encoded bit with probability 1 (the states $|0\rangle,|1\rangle,|+\rangle,|-\rangle$ are eigenstates of the corresponding measurement operators). Hence sifted bits agree perfectly: $Q = 0$, and the sifted key is already a valid shared secret, modulo confirming no eavesdropping occurred.

Security intuition — why eavesdropping is detectable. Suppose Eve intercepts a qubit and tries to learn $a_i$ before Bob measures it. She does not know $b_i$. If she measures in the wrong basis (probability $1/2$ if she guesses uniformly), the state she forwards to Bob is no longer the original state: for example, if Alice sent $|0\rangle$ and Eve measures in the diagonal basis, she collapses the qubit to $|+\rangle$ or $|-\rangle$, each with probability $1/2$, destroying the original information. When Bob later measures this disturbed state in the correct basis (rectilinear, matching Alice's), he now gets the correct bit with probability only $1/2$ instead of $1$, because the state Eve forwarded is unbiased with respect to the rectilinear basis. Formally, for the simplest intercept-resend attack where Eve measures every qubit in a randomly chosen basis and resends the post-measurement state, a short calculation shows that conditioned on Eve guessing the wrong basis (probability $1/2$), Bob's result flips relative to Alice's with probability $1/2$. So the induced error rate on sifted bits is

A full intercept-resend attack on every qubit is therefore detected with overwhelming probability once $m$ (the sample size for error estimation) is moderately large, since $Q = 1/4 \gg 0$ is far from the noise floor of a well-engineered channel (typically a few percent). This is the operational manifestation of the The No-Cloning Theorem Revisited: Eve cannot copy the unknown qubit and measure the copy, and any measurement she performs on the original necessarily perturbs it in a way Bob can statistically detect. More refined attacks (partial measurements, entangling probes) trade off information gain against disturbance, but rigorous security proofs — via the connection between BB84 and entanglement-based protocols, and via smooth min-entropy / de Finetti arguments — show that for any attack, Eve's total information about the final key is bounded by a function of $Q$, and this bound vanishes as $Q \to 0$. This is what justifies aborting above a threshold $Q^*$: below it, privacy amplification can be tuned to erase Eve's residual information.

Honest caveats. BB84's unconditional security proof assumes: an authenticated classical channel (an active man-in-the-middle on the classical channel breaks the protocol via impersonation, unrelated to quantum effects); ideal single-photon sources (real weak-coherent-pulse sources are vulnerable to photon-number-splitting attacks unless decoy states are used); and detectors free of side channels (real detectors have been broken via blinding attacks that exploit detector nonlinearity — a hardware, not protocol, vulnerability). The protocol guarantees information-theoretic security of the ideal mathematical description; deployed systems require substantial engineering to close these side channels.

We trace a small run with $N = 12$ qubits, no noise, and one intercept-resend eavesdropper who measures every qubit in a randomly chosen basis and resends the collapsed state.

(R = rectilinear, D = diagonal; "rand" = a fair-coin outcome forced by measuring in the wrong basis.) Walking through the sifted rounds ($1,2,5,6,7,8,9,12$ — 8 of 12 rounds, close to the expected half):

• Rounds where Eve happened to guess the same basis as Alice (1, 6, 7, 12): the state reaching Bob is undisturbed, so whenever Bob's basis also matches, he recovers Alice's bit with certainty. No error.
• Rounds where Eve guessed the wrong basis (2, 5, 8, 9): Eve's measurement collapsed the qubit into a state unbiased with respect to Alice's original basis. Even though Bob's basis matches Alice's, Bob's outcome is now a fair coin flip independent of $a_i$: each such round has probability $1/2$ of disagreeing with Alice.

Suppose in this run rounds 2 and 9 happen to come out matching by chance and round 5 and 8 come out mismatched. That gives $2$ errors out of $8$ sifted bits, an empirical $Q = 0.25$ — exactly matching the theoretical prediction $Q = 1/4$ for full intercept-resend, derived in the previous section. Alice and Bob's public sample would reveal this elevated error rate; comparing against a threshold (say $11\%$), they would abort, correctly concluding the channel is compromised. Had Eve not intercepted at all, all 8 sifted bits would agree, $Q = 0$ (up to real device noise), and the protocol would proceed to reconciliation and privacy amplification.

Commercial QKD systems from vendors such as ID Quantique and Toshiba deploy BB84 or its decoy-state variants to secure point-to-point fiber links between data centers, banks, and government facilities, typically feeding keys into classical symmetric encryption (AES) rather than serving as a one-time pad due to key-rate limits. National and metropolitan QKD networks — including deployments in Switzerland, China (the Beijing–Shanghai backbone), and South Korea — chain trusted relay nodes running BB84 to extend secure key distribution beyond direct line-of-sight fiber distances. Satellite-based QKD, demonstrated by the Micius mission, uses a BB84-family protocol to distribute keys between ground stations thousands of kilometers apart, motivated by fiber-loss limits that make purely terrestrial long-distance QKD impractical. Standards bodies (ETSI, ITU-T) have begun specifying QKD network interfaces explicitly built around BB84's sifting-and-amplification structure. In the broader research landscape, BB84 is the canonical example used to teach the operational meaning of the No-Cloning Theorem Revisited and serves as the entry point for the more general noisy-channel security analysis developed under Quantum Channels and Operations, where real detector loss, dark counts, and depolarizing noise are modeled explicitly to derive practical, finite-key security bounds.

Ask the tutor: How does the security proof formally bound Eve's information as a function of the observed error rate Q?