What is quantum cryptography and how does it work?

[This is a transcript of the video embedded below. Some parts of the text may not make sense without the graphics in the video.]

If you punch your credit card number into a website and hit “submit”, I bet you don’t want to have twenty fraudulent charges on your bank account a week later. This is why all serious online retailers use encryption protocols. In this video, I want to tell you how quantum mechanics can help us keep secrets safe.


Before I get to quantum cryptography, I briefly have to tell you how the normal, non-quantum cryptography works, the one that most of the internet uses today. If you know this already, you can use the YouTube tool bar to jump to the next chapter.

The cryptographic codes that are presently being used online are for the most part public key systems. The word “key” refers to the method that you use to encrypt a message. It’s basically an algorithm that converts readable text or data into a mess, but it creates this mess in a predictable way, so that the messing up can be undone. If the key is public, this means everybody knows how to encrypt a message, but only the recipient knows how to decrypt it.

This may sound somewhat perplexing, because if the key is public and everybody knows how to scramble up a message, then it seems everybody also knows how to unscramble it. It does not sound very secure. But the clever part of public key cryptography is that to encode the message you use a method that is easy to do, but hard to undo.

You can think of this as if the website you are buying from gives you, not a key, but an empty treasure chest that locks when you close it. You take the chest. Put in your credit card number, close it. And now the only person who can open it, is the one who knows how to unlock it. So your message is safe to send. In practice that treasure chest is locked by a mathematical problem that is easy to pose but really hard to solve.

There are various mathematical problems that can, and that are being used, in cryptographic protocols for locking the treasure chest. The best known one is the factorization of a large number into primes. This method is used by the algorithm known as RSA, after its inventors Rivest (i as in kit), Shamir, and Adleman. The idea behind RSA is that if you have two large prime numbers, it is easy to multiply them. But if you only have the product of the two primes, then it is very difficult to find out what its prime-factors are.

For RSA, the public key, the one that locks the treasure chest, is a number that is derived from the product of the primes, but does not contain the prime factors themselves. You can therefore use the public key to encode a message, but to decode it, you need the prime factors, which only the recipient of your message has, for example the retailer to whom you are sending your credit card information.

Now, this public key can be broken, in principle, because we do know algorithms to decompose numbers into their prime factors. But for large numbers, these algorithms take very, very long, to give you a result, even on the world’s presently most powerful computers. So, maybe that key you are using can be broken, given a hundred thousand years of computation time. But really who cares. For all practical purposes, these keys are safe.

But here’s the thing. Whether or not someone can break one of these public keys depends on how quickly they can solve the mathematical problem behind it. And quantum computers can vastly speed up computation. You can see the problem: Quantum computers can break cryptographic protocols, such as RSA, in a short time. And that is a big security risk.

I explained in a previous video what quantum computers are and what to expect from them, so check this out if you want to know more. But just how quantum computers work doesn’t matter so much here. It only matters that you know, if you had a powerful quantum computer, it could break some public key cryptosystems that are currently widely being used, and it could do that quickly.

This is a problem which does not only affect your credit card number but really everything from trade to national security. Now, we are nowhere near having a quantum computer that could actually do such a computation. But the risk that one could be built in the next decades is high enough so that computer scientists and physicists have thought of ways to make public key cryptography more secure.

They have come up with various cryptographic protocols that cannot be broken by quantum computers. This is possible by using protocols which rely on mathematical problems for which a quantum computer does not bring an advantage. This cryptography, which is safe from quantum computers is called “post-quantum cryptography” or, sometimes, “quantum resistant cryptography”.

Post-quantum cryptographic protocols do not themselves use quantum effects. They have the word “quantum” in their name merely to say that they cannot be broken even with quantum computers. At least according to present knowledge. This situation can change because it’s possible that in the future someone will find a way to use a quantum computer to break a code currently considered unbreakable. However, at least at the moment, some cryptographic protocols exist for which no one knows how a quantum computer could break them.

So, computer scientists have ways to keep the internet safe, even if someone, somewhere develops a powerful quantum computer. Indeed, most nations already have plans to switch to post-quantum cryptography in the coming decade, if not sooner.

Let us then come to quantum cryptography, and its application for “quantum key distribution”. Quantum key distribution is a method for two parties to securely share a key that they can then use to encode messages. And quantum physics is what helps keep the key safe. To explain how this works, I will again just use the simplest example, that’s a protocol known as BB Eighty-four, after the authors Bennett and Brassard and the year of publication.

When physicists talk about information transfer, they like to give names to senders and receivers. Usually they are called Alice and Bob, so that’s what I will call them to. Alice wants to send a secret key to Bob so they can then have a little chat, but she does not want Bob’s wife, Eve, to know what they’re talking about. In the literature, this third party is normally called “Eve” because she is “eavesdropping”, hahaha, physics humor.

So, Alice creates a random sequence of particles that can have spin either up or down. She measures the spin of each particle and then sends it to Bob who also measures the spin. Each time they measure spin up, they note down a zero, and each time they measure spin down, they note down a one. This way, they get a randomly created, shared sequence of bits, which they can use to encode messages.

But this is no good. The problem is, this key can easily be intercepted by Eve. She could catch the particle meant for Bob in midflight, measure it, note down the number, and then pass it on to Bob. That’s a recipe for disaster.

So, Alice picks up her physics textbooks and makes the sequence of particles that she sends to Bob more complicated.

That the spin is up or down means Alice has to choose a direction along which to create the spin. Bob has to know this direction to make his measurement, because different directions of spins obey an uncertainty relation. It is here where quantum mechanics becomes important. If you measure the direction of a spin into one direction, then the measurement into a perpendicular direction is maximally uncertain. For a binary variable like the spin, this just means the measurements in two orthogonal directions are uncorrelated. If Alice sends a particle that has spin up or down, but Bob mistakenly measures the spin in the horizontal direction, he just gets left or right with fifty percent probability.

Now, what Alice does is to randomly choose whether the particles’ spin goes in the up-down or left-right direction. As before, she sends the particles to Bob, but – and here is the important bit – does not tell him whether the particle was created in the up-down or left-right direction. Since Bob does not know the direction, he randomly picks one for his measurement. If he happens to pick the same direction that Alice used to create the particle, then he gets, as previously, a perfectly correlated result. But if he picks the wrong one, he gets a completely uncorrelated result.

After they have done that, Alice sends Bob information about which directions she used. For that, she can use an unencrypted channel. Once Bob knows that, he discards the measurements where he picked the wrong setting. The remaining measurements are then correlated, and that’s the secret key.

What happens now if Eve tries to intersect the key that Alice sends? Here’s the thing: She cannot do that without Bob and Alice noticing. That’s because she does not know either which direction Alice used to create the particles. If Eve measures in the wrong direction – say, left-right instead of up-down – she changes the spin of the particle, but she has no way of knowing whether that happened or not.

If she then passes on her measurement result to Bob, and it’s a case where Bob did pick the correct setting, then his measurement result will no longer be correlated with Alice’s, when it should be. So, what Alice and Bob do is that they compare some part of the sequence they have shared, again they can do that using an unencrypted channel, and they can check whether their measurements were indeed correlated when they should have been. If that’s not the case, they know someone tried to intercept the message. This is what makes the key safe.

The deeper reason this works is that in quantum mechanics it is impossible to copy an arbitrary state without destroying it. This is known as the no-cloning theorem, and this is ultimately why Eve cannot listen in without Bob and Alice finding out.

So, quantum key distribution is a secure way to exchange a secret key, which can be done either through optical fiber or just free space. Quantum key distribution actually already exists and is being used commercially, though it is not in widespread use. However, in this case the encoded message itself is still sent through a classical channel without quantum effects.

Quantum key distribution is an example for quantum cryptography, but quantum cryptography also more generally refers to using quantum effects to encode messages, not just to exchange keys. But this more general quantum cryptography so far exists only theoretically.

So, to summarize: “Post quantum cryptography” refers to non-quantum cryptography that cannot be broken with a quantum computer. It exists and is in the process of becoming widely adopted. “Quantum key distribution” exploits quantum effects to share a key that is secure from eavesdropping. It does already exist though it is not widely used. “Quantum cryptography” beyond quantum key distribution would use quantum effects to actually share messages. The theory exists but it has not been realized technologically.

I want to thank Scott Aaronson for fact-checking parts of this transcript, Tim Palmer for trying to fix my broken English even though it’s futile, and all of you for watching. See you next week.