The 1984 Algorithm That Quantum Computers Still Can't Break
Modern cryptography is a race against compute power. Quantum cryptography changes things. Security is no longer guaranteed by difficulty, but by nature itself. This blog post will walk you through an actual quantum algorithm step by step.
)
You might have heard that quantum computers can break modern cryptography by solving otherwise impossible mathematical challenges, but did you know that the main deal-breaker, Shor’s algorithm, was developed in 1994 long after the first quantum cryptographic algorithms started appearing?
The main issue with modern cryptographic algorithms is that they all rely on one simple principle: It is only secure as long as no one has a lot of computational power or finds a better algorithm. For example, finding factors of a large number gets increasingly difficult for large numbers so it can be used to “prevent” brute-force attacks. But as Peter Shor was able to show later, this can easily be done using a quantum computer.
Researchers started asking a much deeper question early on:
Can we find a cryptographic algorithm, such that its security does not solely rely on computational hardness, but instead is manifested in nature itself?
In 1984, the people Charles Bennett and Gilles Brassard came up with such an algorithm, which is now simply called “BB84”. I want to explain how it works, but in order to do that, I first have to explain how quantum computers work. Specifically, what is it that we call a “qubit” and how does it behave?
Qubits
Quantum physics is weird. Qubits are even weirder for someone coming from classical computers which mainly operate using 0s and 1s. But, in essence, a quantum computer will work similarly to a classical computer by chaining quantum gates together which operate on quantum bits (qubits) to produce some result.
I can only make my point, if you are willing to accept some weird facts about qubits first. If you don’t understand any of these, it might help you that most physicists also do not know why they are true. It just happens to be like that.
Let’s compare qubits to classical bits and introduce a few new concepts:
1. Ones and zeros
Qubits can be 0s and 1s. But they can also be “1 and 0 at the same time”. Or even “pretty 1 but also a bit of 0”. You can imagine it like an arrow where 1 is up and 0 is down. You can measure the "amount of one" and the "amount of zero" depending on how much the arrow points in either direction. If its to the side, both 1 and 0 are equally likely. This arrow representation is also called the Bloch sphere.
)
2. Probabilities
If you measure your qubit, you don’t actually read out the arrow. You either get 0 or 1, just like with classical computers! But: The more it points towards one side, the more likely the outcome is. In the first picture, it would be very likely to measure a 1 and very unlikely to measure a 0. In the second picture, we will always measure a 0. And in the third picture, it’s a 50:50 chance to get either one. It’s also called a Superposition of 0 and 1.
3. Collapse
After you measured the qubit, it changes! The arrow aligns with the direction of your outcome. If you happen to measure a 0 in the first example, the arrow would align with the “down” direction after your measurement. It’s almost like it sneakily rotates so your next measurement will be guaranteed to have the same result. Once you measured a 0, all measurements afterwards will also be a 0. This is a very important concept, because by looking at your qubit, you have actually changed the qubit. There is no way back! This is also called a Collapse of the quantum state.
)
4. Freedom of direction
If that wasn’t confusing enough to you: 1 does not have to be up and 0 does not have to be down. You as the measurer decide in which direction you measure. You could just define your 0 to be on the right and your 1 to be on the left. Then the picture would read like: “pretty 0, but also a bit of 1”, “1 and 0 at the same time” and “exactly 1”. You have the freedom to measure your qubit in any direction. This also means that a qubit in a superposition might look like a pure 0 in another coordinate system. It’s a bit like character encoding where sender and receiver have to agree on one direction otherwise mistakes will be made.
Now, if you are insane enough to accept that there exists such a physical system, which behaves exactly like described and also has this strange fuzziness with probabilities to it, then I can show you how this can be exploited to create a quantum cryptographic algorithm.
The measurement problem
Maybe you already noticed that if you change your qubit by measuring it, this can be exploited to find out if a secret attacker was looking at your data in the middle when sending qubits from A to B.
But “changing by looking at it” only works, if you read data in the “wrong” direction. Take the “exactly 0” example from before. If someone send you this and you measure it in the same direction as it was sent to you, you can easily find out that it was a 0 without changing anything since the arrow already points in the down direction.
)
The idea is that you somehow have to force an attacker to measure in a different direction than you. But how do you do that?
You can’t just agree on a direction with the other party and not tell the attacker. The agreement would need to be done publicly and the attacker would be smart enough to listen in and use the same direction as both of you.
But what if you don’t actually agree on just one direction. What if you agree to use two directions. At random. Completely random for each qubit even. No way the attacker can predict what you will choose! (As we are already in a quantum regime, we can also make use of true randomness!).
I mean, surely, now you ran into the problem that about half of you data turns into complete gibberish because you will happen to choose the wrong direction about half of the time. But maybe that’s exactly what you want! Because your gibberish will be a different gibberish than the gibberish the attacker gets.
Confused? Let’s go over the BB84 algorithm as an example step-by-step.
BB84
We will think of two individuals, (A)lice and (B)ob, trying to establish a secret key over a channel, which might be unsafe.
Step 1
Alice and Bob both agree to use a random measuring direction for each qubit. They decide on two directions (blue/purple) in beforehand and when measuring, they also choose one of these two directions at random. Given two directions, there are now 4 possibilities for “pure” 0 or 1 states.
)
Step 2
Alice sends Bob a long random sequence of qubits. For each qubit she chooses a 0 or 1 at random encoded in a random direction (blue/purple).
)
Step 3
Bob receives this random sequence of qubits and measures each qubit with a random direction (blue/purple). If he happens to choose the same direction, it should yield the same result. Otherwise, it will be something completely different. Like this he gets his own sequence, which might look like this:
)
Step 4
After everything is done, they both compare their results by broadcasting a part of their sequence publicly. There will be one of two scenarios which can happen now:
Scenario 1: Secret attacker
If both parties used the same direction, they would expect a 100% agreement on these qubits. But if there is an attacker looking at the qubits in the middle, it can happen that although both parties used the same measuring direction, they still disagree. As the attacker does not know Alices and Bobs measuring direction in beforehand, best he can do is also guess at random, which will inevitably alter some of the results, which immediately raises suspicion.
)
It is still possible, that just by chance both parties still agree on their results, but the longer the sequence, the more unlikely it is for that to happen. Alice and Bob will just choose a sequence length long enough so they both feel comfortable with it.
Or in other words: “all results agree exactly” is exponentially more unlikely than “at least one of the results does not agree” in the case of an attacker.
Scenario 2: No secret attacker
As they both chose their directions at random, there will be qubits where both of them chose the same direction. If there is no secret attacker, there is a 100% chance that both parties agree on these qubits. They can just check the qubits which were measured in the same direction one-by-one like so:
)
Because they didn’t broadcast the entire sequence, they can just use the matching qubits of the remaining sequence as the cryptographic key, which can then be used for symmetric encryption.
What this means for the future
If Alice and Bob find out that there is a secret attacker looking at their data, there isn’t really anything they can do about it. Best they can do is try again or use a different channel.
Another issue with BB84 is that it’s weak to man-in-the-middle attacks. There could just be some third party E establishing two channels with A and B while pretending to be B and A. But that’s an issue all cryptographic algorithms have, quantum or not. It’s solved by introducing Certificate Authorities.
Furthermore, there are also a lot of problems related to quantum noise, which make algorithms like these hard to implement in practice. The more qubits you want, the more qubits you need for quantum error correction. And currently there exists a limit, where adding any number qubits would require even more qubits for quantum error correction so you don’t actually gain anything from adding more qubits.
We still haven’t reached the critically qubit limit yet, where some of the classical cryptography will start to break. And even then, there are already a lot of newer and better classical algorithms out there, which are not breakable by quantum computers yet.
But some systems still use weak security because its often times non-trivial to quickly “update” large running systems. Furthermore, people are already starting to collect encrypted data just in case it can be decrypted in the future.
It remains to be seen what will happen when the first quantum computers reach the critical threshold.
)
)
)
)
)
)
)
)
)
)