I am writing about Quantum Key Distribution (QKD) in this document, focusing on the BB84 protocol since it is the original and most widely taught version. QKD lets two parties, whom I will call Alice and Bob, establish a shared secret cryptographic key over a channel that could be intercepted by an eavesdropper, with the guarantee that any eavesdropping attempt is detectable due to the fundamental laws of quantum mechanics. I find this genuinely different from classical key exchange methods like Diffie-Hellman, because QKD’s security does not depend on an eavesdropper lacking sufficient computing power; it depends on physical principles that hold regardless of how powerful a future computer, even a quantum one, might become.
History and Background
Quantum key distribution was introduced by Charles Bennett and Gilles Brassard in 1984, and the protocol they proposed is now universally known as BB84 after their initials and the year of publication. Their work built on earlier, unpublished ideas by Stephen Wiesner from around 1970 about “quantum money” using quantum states to prevent counterfeiting, which Bennett and Brassard adapted into a practical key distribution scheme. Since 1984, the field has grown substantially, with the Ekert protocol (E91) introduced by Artur Ekert in 1991 offering an alternative approach based on quantum entanglement, and decades of subsequent research into practical implementations, satellite-based QKD, and commercial QKD systems now deployed in some government and financial networks.
Problem Statement
Alice and Bob want to establish a shared, secret, random binary key over a communication channel that passes through territory potentially monitored by an eavesdropper, whom I call Eve. I want a protocol that lets Alice and Bob detect, with high probability, whether Eve attempted to intercept and measure the key exchange, so that they only use the resulting key if they can be confident it remains secret, discarding the exchange entirely if eavesdropping is detected.
Core Concepts
- Qubit: the basic unit of quantum information, which, unlike a classical bit, can exist in a superposition of states until measured.
- Polarization basis: in BB84, I encode bits using photon polarization, typically choosing between two bases: the rectilinear basis (0° and 90°, representing bit 0 and 1) and the diagonal basis (45° and 135°, also representing bit 0 and 1).
- Measurement collapse: the quantum mechanical principle that measuring a qubit in the wrong basis disturbs its state, an effect I exploit to detect eavesdropping.
- No-cloning theorem: the principle that Eve cannot make a perfect copy of an unknown qubit to measure later without disturbing the original, which prevents her from eavesdropping undetected.
- Public discussion phase: the classical communication step where Alice and Bob compare which bases they used (not the actual bit values) to discard mismatched measurements and estimate the error rate.
- Quantum bit error rate (QBER): the fraction of bits that disagree between Alice and Bob’s sifted key, used as the primary signal to detect eavesdropping.
How It Works
I describe the BB84 protocol step by step, as I understand and use it:
- Alice generates a random string of bits, and for each bit, she randomly chooses one of two polarization bases (rectilinear or diagonal) to encode it as a photon.
- Alice sends this sequence of polarized photons to Bob over a quantum channel.
- For each incoming photon, Bob randomly chooses one of the two bases to measure it in, without knowing which basis Alice used.
- After all photons have been sent and measured, Alice and Bob communicate over a public (but authenticated) classical channel, revealing only which basis they each used for each bit, not the bit values themselves.
- They keep only the bits where their chosen bases matched, discarding the rest; this surviving subset is called the “sifted key.”
- Alice and Bob publicly compare a randomly chosen subset of the sifted key bits to estimate the error rate (QBER); if the bits match perfectly (given their measurement bases matched), those bits should also match in value, assuming no eavesdropping or channel noise occurred.
- If the estimated error rate is below an acceptable threshold, they proceed to use privacy amplification and error correction techniques on the remaining, unrevealed sifted key bits to produce a final, shorter, provably secure shared secret key. If the error rate is too high, they abort, since this indicates likely eavesdropping (or excessive channel noise).
Working Principle
The security of BB84 rests on a beautifully simple quantum mechanical fact: if Eve intercepts a photon and measures it, she has to guess which basis Alice used, since she cannot know it in advance. If she guesses the wrong basis (which happens roughly half the time), her measurement disturbs the photon’s state in a way that introduces detectable errors when Bob later measures it in the correct basis matching Alice’s original choice. Because Eve’s interference is fundamentally undetectable to her without knowing Alice’s basis choice in advance, and because the no-cloning theorem prevents her from copying the photon to measure later without disturbance, any meaningful eavesdropping attempt statistically raises the error rate in the sifted key that Alice and Bob later compare. This gives Alice and Bob a reliable statistical test: if the QBER stays low, they can be confident, to a quantifiable degree, that no significant eavesdropping occurred.
Mathematical Foundation
I represent the four possible photon states used in BB84 using two conjugate bases. In the rectilinear basis, bit 0 is $|0\rangle$ and bit 1 is $|1\rangle$. In the diagonal basis, bit 0 is $|+\rangle$ and bit 1 is $|-\rangle$, where:
$$ |+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle), \qquad |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle – |1\rangle) $$
When Eve (or Bob) measures a qubit prepared in one basis using the other, opposite basis, the probability of obtaining each outcome is exactly:
$$ P(\text{outcome} = 0) = P(\text{outcome} = 1) = \frac{1}{2} $$
which is the mathematical source of the roughly 25% error rate Eve introduces into the sifted key when intercepting and resending: half the time she picks the wrong basis, and of those cases, half the time Bob’s later correct-basis measurement still gives a different result than Alice’s original bit, giving an expected QBER contribution of approximately:
$$ QBER_{Eve} \approx \frac{1}{2} \times \frac{1}{2} = \frac{1}{4} = 25% $$
The final secure key length after privacy amplification is typically bounded using information-theoretic formulas, such as:
$$ \ell \leq n \left(1 – 2 \cdot h(QBER)\right) $$
where $n$ is the sifted key length and $h(\cdot)$ is the binary entropy function, reflecting how much information must be sacrificed to guarantee security given the observed error rate.
Diagrams
flowchart TD
A[Alice generates random bits and random bases] --> B[Alice encodes bits as polarized photons and sends to Bob]
B --> C[Bob randomly chooses a basis to measure each photon]
C --> D[Alice and Bob publicly compare which bases were used]
D --> E[Keep only bits where bases matched: sifted key]
E --> F[Publicly compare a sample subset to estimate error rate QBER]
F --> G{Is QBER below acceptable threshold?}
G -- No --> H[Abort: likely eavesdropping detected]
G -- Yes --> I[Apply error correction and privacy amplification]
I --> J[Final shared secret key established]Pseudocode
function BB84_KEY_DISTRIBUTION(n_bits):
alice_bits = RANDOM_BITS(n_bits)
alice_bases = RANDOM_BASES(n_bits) // each basis: rectilinear or diagonal
photons = ENCODE(alice_bits, alice_bases)
SEND_OVER_QUANTUM_CHANNEL(photons)
bob_bases = RANDOM_BASES(n_bits)
bob_results = MEASURE(photons, bob_bases)
PUBLIC_CHANNEL_EXCHANGE(alice_bases, bob_bases)
sifted_alice = []
sifted_bob = []
for i in range(n_bits):
if alice_bases[i] == bob_bases[i]:
sifted_alice.append(alice_bits[i])
sifted_bob.append(bob_results[i])
sample_indices = RANDOM_SUBSET(len(sifted_alice))
errors = COUNT_MISMATCHES(sifted_alice, sifted_bob, sample_indices)
qber = errors / len(sample_indices)
if qber > THRESHOLD:
return ABORT("Eavesdropping detected")
remaining_alice = REMOVE(sifted_alice, sample_indices)
remaining_bob = REMOVE(sifted_bob, sample_indices)
final_key = ERROR_CORRECTION_AND_PRIVACY_AMPLIFICATION(remaining_alice, remaining_bob)
return final_key
Step-by-Step Example
I walk through a small example with 8 bits for clarity, using R for rectilinear basis and D for diagonal basis.
- Alice’s random bits: 1 0 1 1 0 0 1 0.
- Alice’s random bases: R D R R D D R D.
- Bob’s random bases (chosen independently): R R D R D R R D.
- Comparing bases: position 1 (R=R match), position 2 (D vs R, mismatch), position 3 (R vs D, mismatch), position 4 (R=R match), position 5 (D=D match), position 6 (D vs R, mismatch), position 7 (R=R match), position 8 (D=D match).
- Matching positions: 1, 4, 5, 7, 8. Sifted key from Alice’s bits at these positions: 1, 1, 0, 1, 0.
- Assuming no eavesdropping and no channel noise, Bob’s measured results at these same positions should also read: 1, 1, 0, 1, 0.
- Alice and Bob publicly reveal a sample, say positions 1 and 4, and confirm both read “1” and “1” respectively, giving zero errors in this sample, so QBER = 0%, well below threshold.
- The remaining sifted bits (positions 5, 7, 8: values 0, 1, 0) become the raw material for the final key after error correction and privacy amplification.
Time Complexity
Generating and encoding $n$ qubits takes $O(n)$ time for Alice. Bob’s measurement process also takes $O(n)$ time. The public basis comparison and sifting process takes $O(n)$ time to compare and filter matching positions. Error correction protocols like Cascade typically run in $O(n \log n)$ time due to their iterative block-comparison structure. Privacy amplification using universal hashing takes $O(n)$ time. So the overall protocol complexity is $O(n \log n)$, dominated by the error correction step.
Space Complexity
Alice and Bob each need $O(n)$ classical space to store their bit strings and basis choices, plus $O(n)$ quantum memory or equivalent photon-handling capacity during the transmission phase (though in practice, photons are typically not stored but measured immediately upon arrival, minimizing quantum memory requirements). The public discussion and sifting phase requires an additional $O(n)$ space for shared classical records used during comparison and error correction.
Correctness Analysis
The security proof of BB84 relies on quantum information-theoretic arguments rather than computational hardness assumptions. I rely on two key physical facts: first, that measuring a quantum state in the wrong basis fundamentally and unavoidably disturbs it (a direct consequence of the Heisenberg uncertainty principle applied to conjugate bases), and second, the no-cloning theorem, which prevents Eve from making an undetectable copy of an unknown quantum state to analyze at her leisure. Formal security proofs, developed over the years following the original 1984 paper (notably by Mayers in 1996 and Shor and Preskill in 2000, who connected BB84’s security to quantum error-correcting code theory), establish rigorous bounds on how much information Eve could possibly have gained given an observed QBER, allowing Alice and Bob to apply exactly enough privacy amplification to reduce Eve’s potential knowledge of the final key to a negligible amount.
Advantages
- Security is based on the laws of physics rather than computational hardness assumptions, making it resistant to future advances in computing power, including large-scale quantum computers that could break classical public-key cryptography.
- Eavesdropping attempts are detectable in principle, giving Alice and Bob a built-in intrusion detection mechanism as part of the key exchange itself.
- It provides information-theoretic security, the strongest security notion in cryptography, rather than merely computational security.
- It integrates naturally with classical symmetric encryption (like the one-time pad or AES) once the shared key is established.
Disadvantages
- Current implementations are limited by transmission distance, since photon loss in optical fiber or free space limits practical QKD range without trusted relay nodes or emerging quantum repeaters.
- It requires specialized hardware (single-photon sources and detectors) that is more expensive and complex than standard classical communication equipment.
- It only solves the key distribution problem, not authentication; Alice and Bob still need a pre-shared authenticated classical channel to prevent man-in-the-middle attacks.
- Real-world implementations have historically been vulnerable to side-channel attacks exploiting imperfections in physical hardware, even though the underlying theoretical protocol remains secure.
Applications
I see QKD used today in government and military secure communications, where information-theoretic security justifies the additional hardware cost and complexity. It is also used in financial sector applications, particularly for securing transactions between data centers over dedicated fiber links, in emerging quantum-secured metropolitan networks in cities like Beijing, Vienna, and Geneva, and in satellite-based QKD experiments, most notably China’s Micius satellite, which has demonstrated intercontinental quantum key distribution over free-space links spanning thousands of kilometers.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N_BITS 16
/* Simulates the BB84 protocol classically (no real quantum hardware),
modeling bases as 0=rectilinear, 1=diagonal, and simulating the
measurement disturbance that occurs on a basis mismatch. */
int alice_bits[N_BITS], alice_bases[N_BITS];
int bob_bases[N_BITS], bob_results[N_BITS];
void alice_prepare() {
for (int i = 0; i < N_BITS; i++) {
alice_bits[i] = rand() % 2;
alice_bases[i] = rand() % 2;
}
}
void bob_measure() {
for (int i = 0; i < N_BITS; i++) {
bob_bases[i] = rand() % 2;
if (bob_bases[i] == alice_bases[i]) {
bob_results[i] = alice_bits[i]; /* correct basis: exact result */
} else {
bob_results[i] = rand() % 2; /* wrong basis: random disturbed result */
}
}
}
int main() {
srand((unsigned int)time(NULL));
alice_prepare();
bob_measure();
int sifted_alice[N_BITS], sifted_bob[N_BITS];
int sifted_count = 0;
printf("Position | Alice basis | Bob basis | Match\n");
for (int i = 0; i < N_BITS; i++) {
int match = (alice_bases[i] == bob_bases[i]);
printf(" %2d | %d | %d | %s\n",
i, alice_bases[i], bob_bases[i], match ? "yes" : "no");
if (match) {
sifted_alice[sifted_count] = alice_bits[i];
sifted_bob[sifted_count] = bob_results[i];
sifted_count++;
}
}
int errors = 0;
for (int i = 0; i < sifted_count; i++)
if (sifted_alice[i] != sifted_bob[i]) errors++;
double qber = sifted_count > 0 ? (double)errors / sifted_count : 0.0;
printf("\nSifted key length: %d\n", sifted_count);
printf("Errors detected: %d\n", errors);
printf("Quantum Bit Error Rate (QBER): %.2f%%\n", qber * 100);
if (qber > 0.11) /* commonly cited BB84 security threshold */
printf("Result: Likely eavesdropping detected, abort key.\n");
else
printf("Result: Key exchange considered secure, proceed to error correction.\n");
return 0;
}
Sample Input and Output
Running this simulation (results vary run to run due to randomization, but with no simulated eavesdropper, QBER should be at or near 0%) gives output similar to:
Position | Alice basis | Bob basis | Match
0 | 1 | 1 | yes
1 | 0 | 1 | no
2 | 1 | 0 | no
3 | 0 | 0 | yes
...
Sifted key length: 8
Errors detected: 0
Quantum Bit Error Rate (QBER): 0.00%
Result: Key exchange considered secure, proceed to error correction.
This matches the expected behavior of BB84 without an eavesdropper: roughly half the bits are discarded due to basis mismatches, and the remaining sifted key should show a near-zero error rate.
Optimization Techniques
I use decoy-state protocols to defend against photon-number-splitting attacks that exploit weak coherent laser pulses (used as practical substitutes for true single-photon sources), significantly improving the achievable secure key rate over long distances. I apply efficient error correction algorithms like Cascade or low-density parity-check (LDPC) codes to minimize the amount of information leaked during the classical error-correction discussion phase. I also use optimized basis choice probabilities (biased rather than 50/50 basis selection, as in the efficient BB84 variant) to increase the sifted key rate without compromising security.
Common Mistakes
I have seen people confuse QKD with quantum-resistant classical cryptography (like lattice-based post-quantum algorithms), when these solve different problems: QKD physically distributes a key using quantum channels, while post-quantum cryptography uses classical mathematics believed to resist quantum computer attacks. Another common mistake is forgetting that QKD alone does not provide authentication, leaving the protocol vulnerable to man-in-the-middle attacks unless combined with a pre-shared authenticated classical channel. I also notice people assume real-world QKD implementations are unconditionally secure exactly as the theoretical protocol promises, when practical hardware imperfections have historically introduced side-channel vulnerabilities that theoretical security proofs do not account for.
Further Reading
- Bennett, C.H., Brassard, G., “Quantum cryptography: Public key distribution and coin tossing,” Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, 1984. https://www.sciencedirect.com/science/article/pii/S0304397514004241
- Ekert, A.K., “Quantum cryptography based on Bell’s theorem,” Physical Review Letters, 1991.
- Shor, P.W., Preskill, J., “Simple proof of security of the BB84 quantum key distribution protocol,” Physical Review Letters, 2000. https://arxiv.org/abs/quant-ph/0003004
- Gisin, N., Ribordy, G., Tittel, W., Zbinden, H., “Quantum cryptography,” Reviews of Modern Physics, 2002. https://arxiv.org/abs/quant-ph/0101098
- Wikipedia overview: https://en.wikipedia.org/wiki/BB84
- Nielsen, M.A., Chuang, I.L., “Quantum Computation and Quantum Information,” Cambridge University Press. https://www.cambridge.org/highereducation/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE
