The BB84 Protocol
You can't measure a quantum system without disturbing it
Table of Contents
What Alice Prepares for the Quantum Channel?
The protocol starts with Alice preparing a set of qubits to send to Bob.
These qubits contain the information that will become their shared one time pad, or key.
Alice first generates two random sequences of the same length: one is a random sequence of 0s and 1s and the other is a random sequence of Xs and Zs, representing the basis in which she will prepare her qubits.
Then she will prepare her qubits in a quantum state according to the combination of the basis and the bit value as per the following chart:
| Basis | Bit=0 | Bit=1 |
|---|---|---|
| Z | ||
| X |
But what are these bases and quantum states?
The main point is that measurements in each basis only ever has two possible outcomes:
- and in the Z basis and
- and in the X basis
Such that:
- If we measure the state in Z basis, we will always get
- But if we measure that same state in X basis, we will get a random result, either or , each with 50% chance.
Alice might prepare a set of qubits like this:
| Alice’s random bits | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | … |
|---|---|---|---|---|---|---|---|---|---|---|
| Alice’s random bases | X | X | Z | Z | Z | X | Z | Z | X | … |
| Alice’s sent states | … |
Alice will send these states to Bob and Bob will randomly decide between X and Z as the basis in which to measure each one.
How does Bob make Measurement?
| Bob’s received states | … | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Bob’s choice of bases | X | Z | X | Z | X | X | Z | X | X | … |
| Bob’s measured states | … | |||||||||
| Bob’s decoded bits | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | … |
Bob uses the same table to decode his qubits, that Alice used to prepare her qubits.
When the Alice’s preparation basis and Bob’s measurement bases match, then their bits will match too. But if Alice chooses to prepare Z and Bob chooses to measure X, or vice-versa, then their corresponding bits won’t necessarily match.
A way that they both can agree on a bit string for a one time pad is by publicly telling each other their choice of basis for a particular qubit.
They keep the bits where their bases match, and discard the rest. This is called Basis Sifting.
How does this scheme protect against unnoticed eavesdroppers?
Let’s see what happens when Eve intercepts the qubits that Alice sends to Bob.
She doesn’t know what state those qubits are in, or how Alice prepared them.
From the Uncertainty Principle and No-Cloning Theorem, she can’t just make an identical copy of those qubits to pass along to Bob; because if she could, she would be able to eavesdrop without detection.
Instead, she guesses a basis in which to measure each qubit (very much like Bob), measures them, and them prepares a new set of “spoof” qubits to send along to Bob.
| Alice’s sent states | … | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Eve’s guess bases | Z | X | X | Z | X | Z | Z | X | X | … |
| Eve’s measured and sent states | … |
| Bob’s received states | … | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Bob’s guess bases | X | Z | X | Z | X | X | Z | X | X | … |
| Bob’s measured states | … | |||||||||
| Bob’s decoded bits | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | … |
Now when Alice and Bob talk on the phone to compare their bases, they decide to keep some subset of the received bits but all the bits in the subset won’t match this time, because Bob was measuring the qubits that Eve prepared, not the original that Alice sent.
Now if they compare a subset of their bits (Bit Sifting) with one another, they will see that some bits don’t match and assume there must have been an eavesdropper.
Since Eve was discovered, Alice and Bob will throw away their bits and start the process again.
But is Eve hadn’t listened in, and their chosen subset of bits matched, then they could use the remaining bits, that they didn’t compare, as their shared key
Real Quantum Computers have Noise
Even if Alice’s preparation bases match Bob’s measurement bases, and there is no eavesdropper, there is still a small chance that they will measure different bits due to errors in the quantum computer.
When they are comparing their bits to check for eavesdropper, they need to have some tolerance for errors, before they conclude the flips have been caused by an eavesdropper, and they throw the whole key out.