Quantum Key Distribution for Everyone
This is the story of how Alice and Bob outsmart their nosy neighbor, Eve. You see, Eve is one of those busybodies who just has to know everything about everyone. You know the type.
Eve sits around all day tapping into people’s phone lines and listening in on their conversations. Her favorite pair to listen to is, you guessed it, the best friends Alice and Bob, both physicists, who share a love of cats and qubits.
The only way Alice and Bob can speak privately is in person, but running down the street to a friend’s house every time one wants to share a joke (Q: Why won’t P and X live in the suburbs? A: Because they don’t commute!) is tedious business. One day, the two friends, fed up with Eve learning their secrets, decide to use cryptography.
Alice can send Bob a secret message by encrypting it with a one-time key, which is an unbreakable encryption technique. A one-time key is just that: a key that is used once.
By the time Eve gets her hands on the message, Alice and Bob would have discarded that key and moved on to another. So unless Eve has access to the key, or can accurately predict the key, she cannot decrypt the message.
While Alice and Bob can choose a secret key using their favorite book, How to tell if your cat is plotting to kill you [1], as a codebook, they decide to something a little more…quantum. Namely, they implement the seminal BB84 quantum key distribution protocol proposed by Bennett and Brassard in 1984 [2].
‘Key distribution’ is essentially the process of getting the key to both communicating parties while minimizing the risk of Eve gaining knowledge of the key. In different words, a key distribution protocol’s purpose is to output a key at one end (Alice’s), and a good estimate of that key at the other (Bob’s).
When principles of quantum physics and qubit measurements come into the picture to create secure cryptographic keys, you’ve got quantum key distribution.
Quantum key distribution is essentially made up of two parts. The first is the quantum component, in which quantum principles are used to check for the presence of an eavesdropper and a raw key is generated through qubit measurements. The second is the classical part, in which the final key is distilled from the raw key through what is known as ‘classical post-processing.’ We’re going to stick to the quantum part and discuss BB84.
How the BB84 Protocol Works
(If you are already familiar with quantum computing terminology, and would like to see a basic demo, jump to the Jupyter notebook embedded in the next section.)
BB84 is what is known as a “prepare and measure” protocol in which Alice prepares a sequence of qubits, sends the qubits to Bob, and then Bob measures them. The two discard those for which the measurement bases do not match.
What does this mean? Think about a measurement basis as a particular way to operate on a qubit state. So, let’s say Alice and Bob each have a choice of two operations they can perform on a single qubit, and let’s call them Red (R) and Blue (B).
Suppose Alice has a sequence of 6 qubits and prepares them according to a classical bit sequence 100100, and uses the combination of operations BRRBRB. She sends the sequence to Bob, and Bob randomly selects the combination of operations BRBBRR.
They publicize their operation choices, and pay attention to only those for which the choices match to guarantee that they have the same information on both ends. What I mean by ‘information’ is the classical bits on both ends. Alice has her original bit sequence 100100 and Bob gets a bit sequence as a result of his measurements.
Notice that their choices for the third and sixth qubits do not match, which means they would not necessarily have the same bit values in those positions. This is because of quantum superposition and how the choice of measurement basis affects the outcome, but we won’t get into that here. Suffice it to say that when their choices do not match, they drop that part in the sequence.
Alice and Bob then choose a subset for which they publicize their bit information. In this case, they decide to share the first two bits (depicted by the boxes). If these two bits match, then they can reasonably assume that Eve hadn’t interfered.
If Eve, having learned all about quantum computing because of listening in on their conversations, intercepts the sequence before it reaches Bob, and makes her own set of operation choices, then she would noticeably disrupt the results.
When Alice and Bob realize that their information that should match does not, they know nosy Eve interfered. They drop the whole process and start once more from scratch. They keep dropping the process until Eve finally gets fed up and stops tapping their communication channel. So the next time Alice and Bob perform an eavesdrop check, they find that their information matches and they can use the second part of the sequence that wasn’t publicized as an eavesdrop check (the unboxed part) as a key!
Note that this is an extremely simplified view of the protocol.
How the BB84 Protocol Works — Simple Qiskit Demo
To see how these principles work in action, you can check out this Jupyter notebook. Note that this is only a simplified demo of the protocol, but it makes use of quantum jargon.
(For more quantum computing basics, check out [4]. More notes to come!)
[1] Matthew Inman (The Oatmeal). How to Tell If Your Cat Is Plotting to Kill You. Andrews McMeel Publishing, 2012.
[2] C.H. Bennett and G. Brassard. Quantum cryptography: public key distribution and coin tossing. Proc. IEEE Int. Conf. on Comp. Sys. Signal Process (ICCSSP), page 175, 1984.
[3] Qiskit Textbook
[4] GitHub: quantum-kittens/quantum-computing-basics
