Quantum cryptography
How quantum technologies enable uncrackably secure communication.
In our modern computer world, being able to encrypt messages is not only necessary to keep some information secret from others, but is a key part of technologies such as cryptocurrencies like Bitcoin. Furthermore, the scandals around widespread eavesdropping of intelligence agencies has shown the world that in fact none of the routines used today are really secure. But what if I told you that in ten years all communication will be secure because it is physically impossible to eavesdrop on communication encrypted by quantum cryptography?
Let’s take a few steps back and look at how cryptography on the internet is done today. Current encryption is based on the RSA algorithm (named after its three inventors Rivest, Shamir and Adleman), which is an “asymmetric” encryption system and uses a combination of a public key (a code which you give to everyone) and a private key (a code which you keep to yourself). It is based on number theory and the algorithm relies on the notion of prime numbers. When you encrypt a message with your computer, all it needs to do is simply multiply numbers (which is a very easy task) given by your private key and the public key of the receiver. The receiver can decrypt the large number you sent them by using their private key and your public key.
The “asymmetry” comes from the difficulty of trying to decrypt the message without knowledge of the private keys: obtaining the large number by eavesdropping on the process is easy, but then having to factorise the large number into two prime numbers is completely impossible if the keys are long enough! That’s because factorising a very large number on a classical computer would take so long (even with the largest supercomputers existing) that it’s enough to discourage anyone from trying. While it has not been proven rigorously that factorisation is a “hard problem” in a mathematical sense, i.e. that no algorithm exists which solves it in polynomial computer time, no such algorithms have been found yet and it is believed that they do not exist. In fact, all known classical algorithms take an exponentially large amount computer time.
Even the best classical algorithm scales exponentially with the length of the key, whereas Shor’s algorithm can solve the same problem in polynomial computer time. (Note that the axes are on a double-logarithmic scale, which means that polynomial functions are straight lines.)
While a long key ensures that current computers can’t crack the encryption this also means that RSA is an algorithm which is not mathematically secure, i.e. it could be broken even if larger computers were available. This type of security is sometimes also called computationally secure, i.e. if the key length is chosen sufficiently large, then even supercomputers would take hundreds or thousands of years to crack a message.
Enter quantum computers
So above, we just established that classically, even the best algorithms for cracking RSA encryption scale exponetentially with time. But, in 1997, a breakthrough happened! Peter Shor showed in a seminal paper how one can factorize numbers in polynomial time on a quantum computer. While the implementation is rather technical, you can read a good intro to this concept on this blog post by Scott Aaronson.
Large quantum computers will be able to crack most existing (classical) encryption mechanisms.
There are two reasons however, why you shouldn’t be worried yet that your government will be able to crack your messages to your co-revolutionairies with its new quantum computer any time soon:
Number one: technologically speaking, we’re way off having a quantum computer large enough to factorize any seriously large number. The largest number ever factorised on a quantum computer is somewhere in the hundreds, far from the huge numbers needed to crack RSA. An equivalent measure for the power of quantum computers is their number of qubits (which are the equivalent to classical computer’s transistors). Current quantum computers have a few tens of qubits, whereas a proper realization of Shor’s algorithm would need a thousand times more!
In fact, Shor’s algorithm is one of the most sophisticated quantum algorithms in terms of the number of quantum bits and gates needed, and it is estimated that it will be a few decades until any serious factorization will be performed.
Mathematically secure: Quantum cryptography
Even though it won’t happen until the medium far future, Shor’s algorithm is a serious threat to everything where secrecy is important. From intelligence agencies to company secrets to football strategies — all of this will suddenly not be secure any more!
Fortunately, to most poisons there exists an antidote and for Shor’s algorithm it’s called: quantum cryptography. But it’s not just a mere evolutionary step from current cryptography techniques, it’s nothing short of a reviolution! Why? Because it’s not only computationally secure, but mathematically secure! One can prove that an eavesdropper will NEVER, even with the best (quantum or classical) computer, be able to crack a quantum encrypted message, because the laws of nature prohibit them to do so.
Quantum cryptography is mathematically secure because the laws of nature prohibit eavesdropping on a quantum encrypted message.
Let’s find out how this works in detail! The most transparent quantum cryptography algorithm is also the first one found, the Bennett and Brassard algorithm invented in 1984. It is based on one of the most important features of quantum mechanics: The possibility of forming a superposition between states, for example between 0 and 1 of a quantum bit (qubit).
The BB84 quantum cryptography algorithm
DISCLAIMER: While I tried to write the following as self-contained as possible, it would be far easier to understand if you read at least the beginning of my article on quantum teleportation, in which I explain some of the basic features of quantum mechanics used here (especially superpositions).
The goal of the protocol is that after the execution, Alice and Bob both share the same key with which they can encrypt messages but not evil eavesdropper Eve (a.k.a. Ernst, please pronounce with evil sounding rolling r).
The protocol proceeds as follows: First, Alice creates a bunch of qubits (for example single photons) and prepares each of them in a random state, where she not only chooses “0” or “1” but also whether she prepares “0” or “1” in the z-basis or x-basis. Physically, “z-basis” or “x-basis” in the case of photons mean that she either uses linearly polarized light or circularly polarized light, and “0” and “1” means horizontal/vertical or right-turning/left-turning. After preparing those qubits, she sends them to Bob.
Secondly, Bob measures each qubit in a randomly chosen basis. This in particular means that he might measure in the “wrong” basis, i.e. not the one in which Alice prepared the qubit.
Thirdly, Bob announces in which basis he measured the qubits and Alice says whether he measured in the right basis. If he measures in the right basis, that means that Alice and Bob now share the knowledge about the measurement outcome. For example, if Alice prepared “1” in the z-basis and Bob measures in the z-basis, then he will get “1” and they can use this “1” as a digit of their key. If he would however measure in the x-basis, he would have a 50% chance of getting the wrong result of the measurement. For example, Alice could prepare the qubit in “0” in the x-basis, which is an equal superposition of “0” and “1” in the z-basis. When Bob measures in the z-basis, he therefore has a 50% chance to measure “0” and a 50% chance to measure “1” — This means Alice and Bob cannot use that qubit for their key because in 50% of all cases, they would not have the same number!
In principle, that’s it. Alica and Bob can use all numbers measured in the correct basis as their key. But if Ernst would intercept the transmission and measure the qubits before sending them to Bob, he could alter the results of the outcome of Bob’s measurement. This is why the last step is needed.
Fourthly, on a part of the qubits measured in the right basis (for example half of them), Bob announces his measurement results and Alice the values with which she prepared them. If they now discover that some values don’t match then they can suspect that Ernst had tried to intercept them. Why? That’s because he can only do the same thing as Bob: measure in a random basis. If he now measured in the “wrong” basis and Bob measured in the “right” one, it can happen that Alice and Bob don’t agree on a measurement outcome. Let’s elucidate that with an example. Alice prepares “0” in the z-basis, Ernst catches that qubit and randomly chooses to measure in the x-basis. He has a 50% chance of measuring “0” and a 50% chance of measuring “1”. Let’s say he measures “0” and sends the resulting qubit to Bob. Bob measures in the z-basis (so Alice and Bob agree on the basis in step 3), so he should get the same as Alice without Ernst intercepting. But because Ernst had measured in the z-basis Bob now has a 50% chance of measuring “1”! Of course, he also has a 50% chance of measuring “0” and Ernst would get away unharmed. That is why Alice and Bob have to compare the measurement outcomes of a considerable fraction of the total number of qubits sent, for example half of them.
It is easier to understand this protocol when looking at this table of a few qubits going through this algorithm:
As explained above, the only thing which can go wrong for Alice and Bob is that Ernst measures in the same basis as Alice and Bob because then they would not notice in step 4. The chance for him to get away with this is however (0.75)^N, where N is the number of qubits used to construct the key, i.e. with just 100 qubits in the key the chance of him getting away is just 1 in 10000000000000!
You may ask why Ernst doesn’t just copy the qubits sent from Alice to Bob a couple of times to then find out what Alice prepared. The simple answer is: he can’t!
The base of quantum security: quantum information can not be copied!
This surprising fact going under the name “no-cloning theorem” was only discovered 70 years after the advent of quantum mechanics despite it being proven in literally two lines of calculation. Also the story of its discovery is quite interesting: It happened during the peer-review of some nutjob paper which tried to prove something physically impossible. Despite it contradicting some of the most fundamental notions of physics, the reviewers had a hard time showing where the error was. In the end, they discovered the no-cloning theorem which disproved the paper’s message. This interesting story of how fresh and sometimes crazy ideas trigger discovery can be read about in the book “How the Hippies saved physics” by David Kaiser, a stunning story of how a small group of Berkeley physicists defied the “shut up and calculate” mentality at the time with long bathtub sessions and psychedelic drugs.
So, if there is only one thing which you want to remember from this post then it should be this very fundamental, and counter-intuitive feature of quantum physics:
Unlike classical information, quantum information can not be cloned.
And because of this, quantum cryptography is physically protected from eavesdroppers, i.e. with the exception of technical imperfections due to noise, it can not be cracked.
Quantum cryptography is already used today
Believe it or not, but the state of Geneva in Switzerland already uses quantum cryptography in elections for ten (!) years (I know — what I write about here is so 2k08!). Based on the BB84 algorithm I explained above, the machines delivered by Swiss startup Idquantique combine traditional RSA cryptography with a truly random key created by quantum key distribution. If you want to read more about it, consult this pdf by idquantique and this Scientific American article.
The state of Geneva already uses Quantum Key Distribution for 10 years in its elections.
More recently, an important step towards a global network of secure quantum communication has been made by the implementation of satellite-based quantum key distribution by the Chinese research team around Jian Wei-Pan. This was one of the first fruits harvested from the massive $10bn quantum technologies programe of the Chinese government.
Quantum technologies are on the rise
This demonstration was not only received with cheers in the Western world, even dubbed the “Sputnik moment” of quantum technologies as it showed that China is miles ahead of achieving truly secure communication. Soon after, Europe initiated its €1bn “quantum flagship” with the “quantum manifesto” and even the Trump administration has announced that they would launch a “National Quantum Initiative” in the $10bn region. With other quantum technologies programes launched on a national level all around the world, it is only a matter of a few years until quantum communication and other quantum technologies will be found in consumer-level devices.
Acknowledgements: The presentation of the BB84 algorithm in this post more or less follows a lecture given by Prof. Tommaso Calarco at the IMPRS-QST summer school in June 2018. A great thanks to Ella Crane who gave this article a thorough check before publishing.
This post originally appeared on http://www.manybodyphysics.com, our blog revolving around everything involving the science of many (quantum) things interacting with each other.
