Quantum Key Distribution Workshop[]
Here we will learn how to set up a quantum key distribution circuit, using the BB84 protocol. The circuit itself is very simple, and can be built using only a photon source, an X gate (quantum NOT gate), two Hadamard gates and a measurement device. You don't need any prior knowledge of quantum computing to get started, but you need to understand classical computing terms, such as bits and logical gates.
After you have gone over the basics, you can watch this video for additional info, and to see how the circuit can be built in-game.
Encryption[]
Encryption means scrambling data according to some pattern, so that others cannot read it. Normally you have one party sending some data, they encrypt the data and send it, and when the data arrives at the recipient, that person unscrambles it using some sort of key that only the sender and receiver knows about. If you don't have the key, you can neither encrypt or "decrypt" the data.
The purpose of encryption is protection of data. To keep information away from people that should not have it. It could be long term protection, like some files sitting on a harddrive somewhere for storage, or it could be temporary, like when it's being transmitted over a network.
Encryption Keys[]
Alice and bob wants to communicate, but a third party is listening in. They encrypt the data so that the eavesdropper can't read it.
The keys used to encrypt and decrypt the data must often be shared somehow, before communication starts. This can be a big problem. If we need to communicate the key to eachother, what's to stop an eavesdropper from simply picking that message up?
There are ways to protect the keys whilst they're being sent, some more secure then others, but quantum computers will invalidate many of the protocols we use today.
The eavesdropper has a quantum computer that is able to crack the code, and decrypt the messages.
For example - the RSA system will no longer work, because quantum computers will be able to crack the keys. Various entities all over the world are gearing up towards this, in order to do things like super-efficient data mining, circumventing bank security and listen in on private conversations.
Quantum computing is not only bad though. It also enables some new high security protocols, because in order to "detect" quantum bits, a person must measure the particle that implements it, and it is extremely hard to do that without leaving a trace. In technical terms, you cannot detect which states these particles are in without altering the states (provided the states are properly prepared).
BB84 overview[]
In the BB84 key distribution protocol (as in any other), the goal is to share an encryption key (a string of bits) between two parties, without it being detected by someone else. We will follow the usual quantum computing convension and call these two parties Alice and Bob. Alice is the sender, and Bob is the receiver. Alice will generate a random bit sequence, such as 1001001011110. This key needs to be communicated to Bob, in secret.
The way we achieve that is by sending qubits rather then regular bits. Qubits can be in the regular bit-states 0 and 1, but they can also be in a superposition of these states. A superposition is a mix of 0 and 1. What it means in physical terms is that the qubits are essentially in both states, until we measure them. When
The state of a particle is uncertain until we measure it (in this case by using a weird, foreign-sounding camera).
measuring we will get either 0 or 1 with a certain percentage chance for each. A "50/50" superposition means its a 50% chance to measure 0, and a 50% chance to measure 1. This is due to something called "quantum uncertainty". The states of a particle (for example position, momentum or spin) are not fixed values, but is determined by a probability distribution (often called the wave-function). You cant say "the particle is over there", but you can say "it's a good chance that the particle is over there".
When you measure a particle, however, the superposition is lost. This phenomenon is referred to as "the collapse of the wavefunction", and it's a real physical property of particles. The state will now be definite. Also, there is no way of knowing what the superposition was pre-measurement by looking at the measurement results. The "structure" of the wave function is lost in this process. In the case of a bit - measured states are always 0 or 1, and nothing else, but you could have measured 0 because the qubit was 0 with a 99.99999% chance, or if the qubit was 0 with a 10% chance, or whatever. There is no way of knowing.
This does not mean we can't get an estimate of a superposition. We could run a circuit many times and then look at the average number of zeroes and ones we got from measuring. If we do 1000000 measurements and half of them are 0, we can be pretty sure it's close to a 50/50 superposition. We could also calculate it if we know all the quantum gates that the particle passes through. The BB84 protocol makes both of these type of tests very hard though.
Finally, a qubit works as a normal bit in that we tie the values to some properties of a physical entity, but since we are working on the logical circuit level we don't really care what those properties are. The same thing applies to a normal bit - it is 0 or 1, and that's all we care about. We don't care if those values correspond to voltages in an electric circuit, or mechanical switches, or some guy flipping coins, or whatever. We will work with "abstract qubits", not the physical implementations, in the same way we work with regular bits instead of voltages. There will be a short explanation to some phenomenons here and there, but nothing deep.
The logical circuit[]
In real life, this protocol often uses polarized photons, but we are using a logical circuit so we don't care about how the qubits are actually implemented .To make it simpler, we also don't care about the errors that may occur in a real, physical system.
In our circuit we will use gates that can be toggled on and off. We create qubits using a "photon source", which always start out in the 0 state, then we enable the X gate if we want to flip it to 1. The X gate is the quantum NOT gate). Superpositions are generated
An unassuming BB84 circuit. Lambda means a particle source, X and H represents the gates, and M means a measurement device that measures in the standard computational basis.
by using Hadamard gates. If we pass either 0 or 1 into a(n enabled) Hadamard gate, the qubit will be put in a 50/50 superposition. You could think of the Hadamard initially as being a "random NOT-gate". If you pass a bit value into it (0 or 1), its a 50% chance the value will be NOTed, and a 50% chance it passes through unchanged.
There is a critical difference between a Hadamard gate and that type of randomizer though. If we apply two Hadamard gates in a row, the superposition will go away, and we would get the original value back! Two Hadamard gates cancel echother out. Two randomizer gates would not cancel eachother out. You'd end up with a 50% chance for 0 and a 50% chance for 1, no matter how many of them you put in a row. This cancelation effect is due to the wave nature of particles, and happens because the particle interfere with itself. It is a quantum effect.
Think about what this means. We can create a particle in the 0 or 1 state, then "obscure" it by applying a hadamard gate and then send it. If a third party is measuring the particles they would get 0 or 1 randomly, but the recipient (who knows about the Hadamard gate) can apply a Hadamard gate of his own before measuring to get the original value.
It's impossible to notice this eavesdropper when using the "Hadamard protocol". Unless of course you catch the son of a bitch while he's sitting by the wire.
Does this mean complete security? No. That in itself would not be a safe protocol. What if a third party is trying to listen in, and they know about the Hadamard gate protocol? They could set up their own Hadamard gate before his measuring device, to get the correct values. If they want to go undetected, they could just put another Hadamard gate behind the measurement device, and pass the particle along to the recipient. That would be impossible to detect, because the two pairs of hadamards (blue outlines in the picture) cancel eachother out.
The way get around this is to apply the Hadamard gate randomly to the qubits we send. That way it is impossible for an eavesdropper to know why he gets the measurement results he gets. Lets say he does a measurement and get 0. Did he get 0 because the sender sent 0, or was the qubit in a superposition and he just happened to get 0 by chance? What if he puts a Hadamard gate before the measurement device. Did he just measure 0 because the user sent 0 through a hadamard and he reversed it back to 0, or did he measure 0 because the user sent a qubit without using a Hadamard gate, and his own Hadamard put it in a superposition? It is impossible to say.
BB84 - Step 1
What I just described is the first step of the BB84 protocol. We send N random bits to the recipient, and those N bits are randomly "Hadamarded". When choosing randomly, the chance should be 50/50, so that for each qubit, 0 is as likely as 1, and the chance of the Hadamard being on is the same as the chance of it being off.
BB84 - Step 2
Let's say we sent 8 bits to Bob, each one random, and we randomly apply a hadamard to each bit. A possible sequence of bit values and Hadamards is given in the table below:
| Qubit | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| A: Value | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| A: Hadamard | Off | On | Off | On | On | On | Off | Off |
Now, Bob does not know any of these values. He must randomly Hadamard the incoming bits (in the same way), and measure the results. A possible Sequence could be this:
| Qubit | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| B: Hadamard | Off | Off | On | Off | On | On | On | Off |
What then will he measure? We can find that out by using the Hadamard cancelation principle. If his Hadamard gate is off, and Alices too, he will measure exactly the value that Alice prepared. The same thing applies if both of them had their Hadamard gates on. Otherwise the bit will pass through one hadamard, and he will measure the qubit in a superposition, so 0 or 1 is equally likely. Lets complete the table:
| Qubit | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| A: Value | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| A: Hadamard | Off | On | Off | On | On | On | Off | Off |
| B: Hadamard | Off | Off | On | Off | On | On | On | Off |
| SUPERPOSITION? | No | Yes | Yes | Yes | No | No | Yes | No |
| B: Value | 1 | ? | ? | ? | 0 | 1 | ? | 0 |
A question mark means he could have measured either 0 or 1, and we don't really care which.
BB84 - Step 3
At this point, Alice and Bob is sitting on two different sequences of bits, but some of the bits are the same - namely the ones where they chose the same Hadamard state. Step 3 of this process is for Bob to send his Hadamard sequence to Alice. He should not, under any circumstances, send his actual bit-values, but the Hadamard sequence is fine. It can even be sent publicly, because if a person does not have the qubit values, this information is useless.
The way he does this is to send 8 bits back to Alice, each bit being 0 if his Hadamard was off, and 1 if it was on. He would thus send Alice the sequence: 00101110.
BB84 - Step 4
When alice receives Bobs Hadamard sequence, she translates it to "On and Offs", and matches it with hers. Whereever they have the same value, he must have measured the bit value she prepared. Of course, this would coincide with the SUPERPOSITION row of the last table, so at this point, alice knows that Bob got qubits 1,5,6 and 8 right, so she scratches the other qubits from her key, and end up with the key 1010.
Bob still doesn't know which ones he got right, so she needs to communicate that back to Bob. She does this by sending a bit sequence to Bob where 0 means he got his measurement wrong, and 1 means he got it right. This sequence would therefore be:
10001101
BB84 - Step 5
Bob receives the bit sequence and picks out qubits 1,5,6 and 8. This gives him the key 1010. Finally they both have the same key. They lost half of the initial bits, but they now have a secure 4-bit key.
This is the table of what Bob knows now. The ?'s in the last table has been replaced by random bits just to show what "he's seeing".
| Qubit | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| B: Hadamard | Off | Off | On | Off | On | On | On | Off |
| B: Value | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| Keep | Yes | No | No | No | Yes | Yes | No | Yes |
| Key | 1 | 0 | 1 | 0 |
Security[]
First of all, we need to acknowledge something - this is a very short key. Also, you loose half the sequence on average, so even though they sent 8 qubits, the key is only 4 bits. They could just as well have agreed on sending 18465 bits instead of 8 though, which would have given them a lot of redundancy, and a massive key.
Let's say we use a large key then, how does that make the protocol secure? How can Alice and Bob be sure that nobody has been listening in on their conversation? How does Bob know his kid pictures wasn't "NSA'ed"? How does Alice know her medical history wasn't "Microsofted"? Well, they don't. There is no 100% fool proof way, of course, but they can sacrifice a few of the bits they agreed on to see if someone has been mucking around with the particles. The only thing they can be sure of is that if they don't encrypt their data - those things will happen. Alices medical history will be used to aggressively and intrusively target her with sketchy medicine commercials. Little Bobby Jr's pool-party pics will be whacked off to by some Google engineer or Facebook employee sitting in an office basement somewhere. Or he could be droned? A glitch in a system somewhere and who knows..
The reason why this protocol is secure is because of the randomness. By using random bit values and random "Hadamarding", an eavesdropper can never be sure if he measured 1 because 1 was the actual value sent, or because he measured a superposition and happened to get it. If he measured a superposition, that means the superposition is lost, and there is no way for him to know if it was in a superposition or not. In short - he will have tampered with the data, and no matter what he tries to do in order to rectify this (re-apply his own Hadamard gates or w/e) he will be wrong about half of the time, and the values Bob measure will not be the expected ones. Again, Alice and Bob can sacrifice values later to detect any discrepancies, but we will not get into that here.
How to encrypt data (optional)[]
If you have shared a key between two parties in Minecraft, using the BB84 circuit, how can you use the key to send encrypted data? One way is to simply XOR anything you send with the key, and send that value. When the recipient gets the value, he can XOR it with the key to get the original data back. It's very simple.
Lets say i want to send the bits 10010011, and the key is 01100111. We XOR the two together:
| DataToSend | 10010011 |
| Key |
01100111 |
| XOR | 11110100 |
The recipient will get the XORed value, and does an XOR of that and the key to decrypt it.
| DataReceived | 11110100 |
| Key |
01100111 |
| XOR | 10010011 |
We see that the DataToSend value equals the XOR value in the recipient table.
Caution![]
I just want to point out: Don't use this system to share important, real information... it's just a (relatively) fun way to learn how quantum key distribution and encryption works. Don't send your creditcard information through some cable in some weird Minecraft server thinking it's safe. This is just a simulator.
I know this is obvious, but still. Don't...