Understanding Quantum Cryptography

When I first started studying Post-Quantum Cryptography (PQC) for my Masters, I was a bit confused about the relationship between Post-Quantum Cryptography and Quantum Cryptography. Judging by the names, one could erroneously conclude that Post-Quantum was the sequel or the better version that followed after Quantum Crypto. The truth is that Quantum and Post-Quantum Crypto are completely different and one does not precede the other. In fact, they are just two different solutions to the same problem: How do we do secure key exchanges in the presence of Quantum adversaries (aka. Quantum Computers)?

Given that most of my time has been spent studying PQC, I thought it would be fun to mix it up and explore Quantum Cryptography. In this post we will mostly focus on the very popular BB84 Quantum Key Distribution Scheme.  If you are completely new to the world of Cryptography, I highly recommend taking a look at one of my older posts about Demystifying Cryptography. Otherwise let's jump into this fascinating subject!

* Recently revived my old Twitter account. Follow me for more crypto/hacking content!
Follow @konukoii

The Problem

Today most of our Key Exchange cryptosystems/algorithms (e.g RSA, DSA, ECDSA, ECDH, ...)  are based on mathematically intractable problems such as the Factoring problem and the Discrete Logarithm problem.

Factoring

Given n; compute p:  n = p⋅q

Discrete Logarithm

Given p, g, y; compute x:   y = gx (mod p)

If you choose the proper parameters, mainly choose really big primes, this problem becomes really complicated for current classical computers to solve in a reasonable amount of time. We have algorithms to solve these problems that run in exponential time --really slow. For the past ~30 years we have been using these cryptosystems without any major problems because of this. However, with Quantum computers in the horizon, we might be running into a bit of a problem.

In 1994, mathematician Peter Shor came up with a quantum algorithm (algorithm only quantum computers can run) that can be used to quickly solve these two problems sub-exponential time. In other words, a Quantum Computer could easily compromise all secure communication that's happening right now on the internet.

The cryptographic research community saw this issue and started focusing their efforts on studying new cryptosystems that could keep our communications safe in the presence of Quantum computers. This is where the study of Quantum and Post-Quantum cryptography come into play, as they propose new alternative systems.

Quantum Computing Basics

As we saw in the previous section, the main issue we are trying to solve is that of securely exchanging a key between two parties (Alice and Bob). Quantum Cryptography seeks to do this key exchange by taking advantage of the physical properties of polarized photons (light).

Photon Polarization

The amazing thing about photons is that they behave as both waves and particles (In fact, this behavior is what sparked the whole study of quantum properties in the first place). This means that we can shoot a photon through a filter and polarize it.

To detect a polarized photon using a filter we must use a filter of the same polarization or otherwise the photon will be destroyed. In a bit, you will see how this "one-way" property is the key to avoid eavesdroppers.

Heisenberg Uncertainty Principle

The Heisenberg Uncertainty principle states that it is not possible to measure the quantum state of any system without disturbing it. In other words, there is no way for anyone (e.g. an eavesdropper) to figure out the state of a polarized photon without measuring it.

With those two things in mind lets look at the Actual Quantum Key Exchange!

Quantum Computing Key Exchange

So let's take a look at the BB84 Quantum Key Distribution Scheme and how it works.

Setup

Alice will have a photon beam with a set of two bases with which she can polarize photon on a total of 4 different ways. Each of these polarization will be assigned a bit value

Bob will have 2 filter he can use to measure these photons:

Exchange

Step 1. Alice chooses a random sequence of polarized photons which she sends to Bob

Step 2. Bob measures the photons polarization by randomly choosing a sequence of bases.

Step 3. Bob tells Alice which basis he used for each photon received.

Step 4. Alice tells Bob which bases where correct.

Step 5. Alice keeps only those photons that Bob managed to correctly measure.

Step 6. Both Alice and Bob now have the same binary sequence.

Why is this secure?

Now imagine that between Alice and Bob is an eavesdropper Eve which has the same equipment as them both.

Due to the Heisenberg Principle,we know that if Eve wants to eavesdrop, she can't simply passively eavesdrop in the conversation. If she wanted to figure out the polarization of the photons sent through the wire, she has to actively test different filters. With every filter she tests, she has a 50% chance of choosing the right filter, otherwise she will destroy the photons being sent.

Let's assume that every time Eve gets a proper guess she resend that same photon to Bob. What'll happen is that Eve will obtain about 50% of the data sent by Alice, but Bob will obtain a 25% of that data. That's going to be the first warning sign, as Bob is going to realize he simply got substantially less data than he expected. Furthermore, when Bob checks with Alice which basis he correctly used (Step 4-5), he will notice a 25% error discrepancy in which, even though he used the proper basis, he did not measure a photon. This reveals there the presence of Eve.

Take a look at the follow example:

There is still one minor issue we haven't discussed which is Man-in-the-Middle attacks. In these types of attacks, Eve actively sits between Alice and Bob sending communications to both of them pretending to be the other. Multiple papers, including the original BB84 paper, have already considered this issue and have presented authentication techniques that allow both parties to validate each other.

Real Life Implementations

You may be thinking this is all theory, but in reality there are already a couple of scientific and commercial applications being used today. Here are a few interesting examples:

• DARPA Quantum Network: A hybrid VPN that is fully compatible with conventional Internet hosts, routers, etc. and works with all the common public-key mechanisms (3DES, SHA1, ...) but uses Quantum Cryptography for all its key exchanges.
• MagiQ Technologies: MagiQ sells quantum-key distribution box that is claimed to be the first commercially available of its kind. It is a $50,000 unit that contains a photon transmitter/receiver that can be interconnected with other units via optic lines. It is intended to generate keys once a second to encrypt access traveling over fiber optic lines.
• China's QUESS: QUESS is a space program intended to experiment with laser communications and space-to-ground quantum communications.

Quantum vs. Post-Quantum

Now that you better understand the ideas behind Quantum Crypto you might be wondering how it differentiates itself from Post-Quantum Crypto (PQC). While I will post a more in-depth explanation on PQC in a future post, I wanted to leave you with a quick idea:

• Quantum Cryptography: Focuses on doing a key exchange via an external channel. It relies on physical quantum properties and assumes that a all parties can be connected in such a way that they can send photons to each other. In other words, this solution relies heavily on physics to implement a secure key exchange.
• Post-Quantum Cryptography: Focuses on doing a key exchange using mathematical problems that are hard for both Quantum and Classical computers to solve. They don't require separate channels (meaning it can happen over insecure channels) or any specific devices. This solution is essentially a purely mathematical solution that can be implemented pretty much anywhere.

Post-Quantum Cryptography is definitely the future of commercial cryptography as it can be implemented wherever we want without any special materials/devices. On the other hand, Quantum Crypto is still fascinating and could motivate further understanding of the physical properties of our universe. Regardless, both fields of study are being heavily funded right now and there is certainly a lot of interesting developments happening every day.

Final Thoughts

As I stare out into the night sky tonight, I wonder what ideas we will come up next... (I also wonder if that Chinese satellite is beaming photons at me right now 🙂 ). Ultimately, Quantum physics presents fascinating challenges and chances for incredible discoveries. I wouldn't be surprised if in the next few decades we see changes in technology and communication beyond our wildest expectations. I hope you enjoyed this post, as always, feel free to contact me with any questions or comments. CryptoCheers!

Further Reading

I consulted the following sources when writing this post. I definitely recommend taking a look at these if you want to plunge deeper into this subject:

• J. Aditya & P. Shkar Rao's Quantum Cryptography
• Petra Pajic's Quantum Cryptography Bachelor Thesis
• C. Bennet & G. Brassard's Quantum Cryptography: Public key distribution and coin tossing