Imagine Alice and Bob want to send secret messages to each other. They need to agree on a secret key โ a shared piece of information used to encrypt and decrypt messages. The problem: how do they agree on this key if their communication channel is public and anyone can listen?
Key Distribution
A cryptographic protocol where two parties (Alice and Bob) can agree on a secret key by communicating over a non-secure channel โ a channel that anyone can observe.
The Classical Approach and its Weakness
Classical cryptography solves this using mathematically hard problems. RSA, for example, relies on the fact that multiplying two large primes is easy, but factoring their product is believed to be hard. Alice and Bob exchange public information derived from these hard problems, and only they can compute the secret key.
The fundamental problem: classical security assumes that certain computational problems are hard. But this is only a conjecture โ we don't have a proof. Worse, Shor's quantum algorithm can factor integers in polynomial time, breaking RSA entirely on a sufficiently powerful quantum computer.
Quantum cryptography is fundamentally different. Instead of relying on computational hardness (which could be defeated by better algorithms or faster computers), it relies on the laws of physics โ specifically, quantum mechanics. No amount of computation can break it, because the security comes from nature itself.
The Core Idea
The key quantum mechanical property we will exploit is: measuring a quantum state disturbs it. If Eve tries to listen in by measuring the qubits Alice sends to Bob, she inevitably leaves a detectable trace. Alice and Bob can check for this trace and know if their channel is compromised.
Classical
Copying information leaves no trace. Eve can tap the wire and forward identical copies โ Alice and Bob never know.
Quantum
Measuring a qubit in the wrong basis collapses its superposition. The forwarded qubit is now a different state. This error is detectable!
Ex 1.1Why can't Eve just copy the qubit?
Eve wants to intercept Alice's qubit, make a copy, keep the original, and forward the copy. What fundamental theorem prevents this?
The No-Cloning Theorem states that it is impossible to create an identical copy of an arbitrary unknown quantum state. Eve cannot clone the qubit โ she must measure it, which disturbs it.
Ex 1.2Security basis
Classical RSA security is "computational" โ it assumes factoring is hard. What kind of security does quantum cryptography provide?
Information-theoretic (or unconditional) security โ based on the laws of physics, not computational assumptions. No algorithm, even a quantum one, can break it.
Section 02
The BB84 Protocol
BB84 is the first and most famous quantum key distribution protocol, invented in 1984 by Charles Bennett and Gilles Brassard. It allows Alice and Bob to agree on a secret key using a quantum channel, even if an eavesdropper (Eve) is listening.
The Two Bases
BB84 uses two measurement bases, each with two orthogonal states:
โ basis (Z)
|0โฉ encodes bit 0 |1โฉ encodes bit 1
โ basis (X)
|+โฉ encodes bit 0 |โโฉ encodes bit 1
The key property: measuring in the wrong basis gives a random result with probability 1/2.
Why random?
|โจ0|+โฉ|ยฒ = |โจ0|โโฉ|ยฒ = |โจ1|+โฉ|ยฒ = |โจ1|โโฉ|ยฒ = 1/2 โ If you measure |+โฉ in the Z basis, you get 0 or 1 each with 50% probability. Completely random!
The 6 Steps of BB84
1
Generation: Alice generates a random sequence of bits (0s and 1s) and for each bit, randomly chooses a basis (โ or โ). She encodes each bit as the corresponding qubit.
2
Transmission: Alice sends all qubits to Bob over the public quantum channel.
3
Reception: Bob, for each qubit, independently and randomly chooses a measurement basis. He records the result of each measurement.
4
Basis comparison: Alice and Bob publicly announce which basis they used for each position (NOT the bits themselves). They keep only the bits where they happened to use the same basis โ about 50% of bits on average.
5
Security check: Alice and Bob publicly compare a small random subset of their kept bits. If an eavesdropper was present, these bits will contain errors. Too many errors โ abort.
6
Secret key: If the security check passes, the remaining unpublished kept bits form the shared secret key.
A Concrete Example
Position
1
2
3
4
5
6
7
8
9
10
Alice bit
0
1
0
0
1
0
1
0
0
1
Alice basis
โ
โ
โ
โ
โ
โ
โ
โ
โ
โ
Tx qubit
|0โฉ
|โโฉ
|+โฉ
|0โฉ
|1โฉ
|0โฉ
|โโฉ
|+โฉ
|0โฉ
|โโฉ
Bob basis
โ
โ
โ
โ
โ
โ
โ
โ
โ
โ
Bob bit
0
?
0
?
1
?
?
?
0
1
Match?
โ
โ
โ
โ
โ
โ
โ
โ
โ
โ
Kept bit
0
โ
0
โ
1
โ
โ
โ
0
1
? = random measurement (wrong basis) ยท Green = matched basis, kept ยท Discarded when bases differ
After comparing bases, Alice and Bob share positions 1, 3, 5, 9, 10 โ their kept bits form the raw key 00101.
Click "Run BB84" to simulate one round. Each run generates random bits and bases.
Ex 2.1Basis mismatch probability
Alice chooses each basis randomly (50% โ, 50% โ). Bob does the same independently. What is the probability that their bases match for any given bit?
What happens if Eve intercepts the quantum channel? Let's trace exactly what occurs.
Eve's Dilemma
Eve sits between Alice and Bob: A โ E โ B. She must measure each qubit to learn information, then forward something to Bob. But she doesn't know which basis Alice used โ she must guess.
Why Eve Gets Caught
Eve guesses the wrong basis 50% of the time. When she measures in the wrong basis:
Example:
Alice sends |0โฉ (Z-basis, bit 0). Eve measures in X-basis โ gets |+โฉ or |โโฉ randomly, say |+โฉ. Eve forwards |+โฉ to Bob.
Bob measures
in Z-basis (matching Alice): P(Bob gets 1) = |โจ1|+โฉ|ยฒ = 1/2 โ error! Bob should have gotten 0.
Net effect:
When Alice and Bob use the same basis, there's a 25% chance of an error (50% Eve uses wrong basis ร 50% Bob then gets wrong bit). This error is detectable in the security check!
The probability of Eve NOT being detected on Np published bits, given that she is eavesdropping, is:
P(no detection) = P(no errors on Nโ bits) = (1/2)Nโ
Even with 20 published bits, P(detection) > 99.9999%!
Worked Example with Eve
Position
1
2
3
4
5
Alice bit
0
1
0
0
1
Alice basis
โ
โ
โ
โ
โ
Tx qubit
|0โฉ
|โโฉ
|0โฉ
|+โฉ
|1โฉ
Eve basis
โ
โ
โ
โ
โ
Eve reads
0
?
?
0
?
Eve forwards
|0โฉ
|0โฉ or |1โฉ
|+โฉ or |โโฉ
|+โฉ
|+โฉ or |โโฉ
Bob basis
โ
โ
โ
โ
โ
Bob reads
0 โ
? (rnd)
? (rnd)
0 โ
? (rnd)
Bases match?
โ
โ
โ
โ
โ
Error possible?
No
Yes 50%
Yes 50%
No
Yes 50%
Green = correct reading (Eve used same basis as Alice) ยท ? = random result (wrong basis)
In the security check (step 5), Alice and Bob compare some of their kept bits. If Eve was eavesdropping, errors appear. With enough published bits, Eve is virtually certain to be detected.
Detection probability vs. number of published bits. Drag the slider.
10
Ex 3.1Error rate due to Eve
When Eve eavesdrops on BB84, what is the expected error rate on bits where Alice and Bob use the same basis? (Hint: think about how often Eve guesses wrong and what happens then.)
Error rate =
50% of the time Eve picks the wrong basis. When she does, she forwards the wrong state, and Bob has a 50% chance of getting the wrong bit. So error rate = 0.5 ร 0.5 = 0.25 = 25%.
Section 04
BB84 Analysis โ Key Rate and Detection Probability
Let's quantify how BB84 works in practice.
Key Generation Rate
Alice generates N₀ bits. After basis comparison, they share roughly N₁ ≈ N₀/2 bits (50% basis match). They publish Nᴩ ≈ αN₁ bits for the security check, with α ∈ [0,1]. The secret key has size:
N ≈ (1−α)/2 · N₀
Half the bits are lost to basis mismatch, a fraction α goes to the security check
Detection Probability
Given that Eve is eavesdropping, and Nโ bits are published for checking:
P(detect)
= P(at least one published bit has an error) = 1 โ P(no errors)
Critical limitation: This analysis assumes a perfect channel. In reality, channels have noise (photon loss, detector errors, etc.) that causes errors even without an eavesdropper. The simple BB84 above does NOT work in the presence of such errors โ post-processing is needed (see Section 5).
Secret key size vs. number of bits Alice generates, for different values of ฮฑ.
0.20fraction published for security check
Ex 4.1Secret key size
Alice generates Nโ = 10,000 bits. She uses ฮฑ = 0.5 (half the kept bits for security check). How many bits are in the final secret key?
In the real world, quantum channels are noisy. Even without an eavesdropper, Bob may receive corrupted qubits. For example, a measurement device might flip a bit with probability p. This means that even with matching bases, some bits will be wrong.
Real scenario: Alice has xA = [0,1,1,0,...] after basis matching. Bob has xB = xA โ n where each noise bit nแตข = 1 (error) with probability p and nแตข = 0 (correct) with probability 1โp.
The Three Post-Processing Steps
Step 1 โ Adaptive Security Check
Instead of a hard threshold, estimate the channel error rate:
pฬ = Nerr / Np
where Nerr is the number of erroneous bits among the Np published bits
If pฬ > ฮณ
โ eavesdropper detected (threshold ฮณ is set in advance). Abort.
If p̂ ≤ γ
→ proceed to error correction. The noise is considered acceptable.
Step 2 โ Error Correction
Alice and Bob need to reconcile their strings. They use a classical error-correcting code, but it must be done carefully to avoid revealing xA to Eve.
Alice encodes
Using a systematic linear code: cA = [xA | pA] where pA is the parity part.
Alice sends
Only pA (the parity bits) over the public classical channel. This is secure because many xA values produce the same parity.
Bob constructs
cB = [xB | pA] and decodes it to recover xA (if there are not too many errors).
Why is sending pA secure? The parity bits do not uniquely determine xA. There are many valid codewords with the same parity โ Eve cannot recover xA from pA alone.
Step 3 โ Privacy Amplification
Even if error correction succeeds, Eve may have gained some partial information about xA by eavesdropping (information leakage). Privacy amplification removes this partial knowledge.
Privacy Amplification
Alice and Bob apply a shared hash function to their (now identical) string xA:
x = hash(xA)
The output x is the final secret key. The hash compresses xA into a shorter string. The key insight: even if Eve knows a few bits of xA, she knows essentially nothing about hash(xA) if the hash is well-chosen. The information leakage can be estimated from pฬ.
Security Check
Estimate pฬ from Nโ published bits. If pฬ > ฮณ โ abort.
Error Correction
Exchange parity bits publicly. Bob recovers xA.
After error correction, Alice and Bob share the same string xA. But Eve may know some bits of xA. Why does applying hash(xA) help?
A good hash is a many-to-one function: many inputs map to the same output. Even if Eve knows some bits of x_A, she cannot determine hash(x_A). The hash "amplifies" Eve's partial ignorance into complete ignorance of the final key.
Ex 5.2Why is error correction needed?
If Alice and Bob share raw strings that differ in a few bits, can they just skip error correction and use privacy amplification directly?
No. Privacy amplification requires Alice and Bob to apply the SAME hash to the SAME input. If their strings differ, they will compute different hashes and end up with different keys โ the whole point of the protocol fails.