Post-Quantum Cryptography, Part 1: Quantum Computing

This was originally published on my blog.

Anyone who can contemplate quantum mechanics without getting dizzy hasn't understood it.

- Niels Bohr, one of the fathers of quantum mechanics

I would like to discuss the two currently favored proposals for post-quantum cryptography. I would also like to differentiate post-quantum cryptography from quantum cryptography. To do so, I must begin with a brief overview of quantum mechanics. This post will cover this brief history and touch on quantum computing's impact on classical encryption standards. Follow-up articles will discuss the proposals for post-quantum cryptography. I have undergone no formal study of quantum mechanics, but I will try my best to illustrate the relevant points. This information is based on papers and articles I have read; I make no claim to being a quantum mechanics expert.

The Double-Slit Experiment

In 1801, a scientist named Thomas Young performed an experiment¹ involving light and the behavior it exhibited when shone against a screen with two slits. Young observed that the light, instead of displaying two bars of light as he would have expected when shown against two slits in a screen, fanned out in a pattern of light and dark stripes. Young hypothesized that light was a form of wave, which would explain the pattern of stripes. As the wave of light hit the screen, it bent around the slits and collided with itself, creating the pattern of stripes. Young's double-slit experiment demonstrated that light behaves like a wave.

Albert Einstein, however, had a different theory. He argued that only if light were actually made up of tiny particles - photons - could the photoelectric effect of the pattern of stripes be explained. If light were a series of photons, then the beam of light hitting the screen scattered the beam of photons. The individual particles interacting with each other on the other side of the slits created the pattern of dark and light stripes. Einstein hypothesized this in 1905, although he was not believed at the time. Einstein ended up winning the Nobel Prize for his paper on this topic. We now know that light can, in fact, behave as both a wave and a particle. This concept is known as wave-particle duality.

Modern physicists, recreating a form of Young's experiment, sent individual photons through a two-slit screen. The expectation was that the pattern of stripes behavior would not occur, as only a single photon was sent through the screen at a time. However, the results displayed the same pattern of stripes, as if the photons had been interacting as in the earlier experiments. This confounded physicists. There is no explanation for this behavior in classical physics.

It is, instead, explained by quantum physics.

There are two theories among quantum physicists to explain the pattern of stripes behavior of the single photon experiment.

Superposition

The first theory is superposition. This idea focuses on what we know of the photon. We know that it leaves its original filament and we know that it strikes the screen somewhere. Everything else about the state of the photon is unknown. Because the path of the photon is unknown, superposition states that the photon passes through both slits simultaneously. Its two states interfere with each other as if two photons were colliding and that is why the striped behavior is observed. How can the single photon pass through both slits? Superposition argues, essentially, that if we do not know what the particle is doing, then it is doing everything. The photon is in a superposition of states. This idea is popularly known in the form of Erwin Schrödinger's cat thought experiment. Schrödinger's cat is the idea that the state of a cat in a box with a vial of cyanide is unknown. Either the cat is alive or it has trodden on the vial, shattered it, and is dead. Since the state is unknown, the cat is simultaneously alive and dead. It is in a superposition of states. It is only upon removing the lid, directly interfering to observe, do the states converge on one of the possibilities.

Many-worlds

Are you getting dizzy yet? The alternative quantum theory to the double-slits experiment is no less bizarre. It is known as the many-worlds theory. The theory essentially uses Schrödinger's thought experiment as a literal explanation of the behavior of the universe(s). The many-worlds theory states that when the state of the photon (or cat) becomes unknown, the universe divides into multiple universes, one for each possible state. In one universe, the photon goes through the left slit. In another universe, the photon goes through the right slit. These two universes interfere with each other in some way, causing the striped pattern of light. This literal interpretation is known as the Everett Postulate:

All isolated systems evolve according to the Schroedinger equation

The Quantum Computer

Regardless of which theory is correct, quantum mechanics answers many questions about the state of our universe. It also inspired David Deutsch, a British physicist, to begin working on the concept of quantum computing.² It was commonly assumed that computers operated according to classical physics. Deutsch believed they should instead obey quantum physics, as the laws of quantum physics were more fundamental. In Deutsch's first paper on the subject, he explained how quantum computers might operate. To describe this, I am going to borrow a passage from Simon Singh's excellent book, The Code Book:

Imagine that you have two versions of a question. To answer both questions using an ordinary computer, you would have to input the first version and wait for the answer, then input the second version and wait for the answer. In other words, an ordinary computer can address only one question at a time, and if there are several questions it has to address them sequentially. However, with a quantum computer, the two questions could then be combined as a superposition of two states and inputted simultaneously - the machine itself would then enter a superposition of two states, one for each question. Or, according to the many-worlds interpretation, the machine would enter two different universes, and answer each version of the question in a different universe. Regardless of the interpretation, the quantum computer can address two questions at the same time by exploiting the laws of quantum physics.

Just as classical computers represent data in bits (either 0 or 1), quantum computers represent data in qubits, or quantum bits. A qubit similarly represents either 0 or 1 but does so typically through the polarization of photons. And of course, a qubit can be both 0 and 1 at the same time, in a superposition of states (or in a multiverse). Instead of tackling one operation at a time, a quantum computer could tackle xⁿ operations at a time, where x is the number of directions the system vibrates or spins photons and n is the number of photons available to the system. Depending on your quantum theory, a quantum computer could perform xⁿ operations simultaneously or would, in fact, be xⁿ computers, each in a separate universe, each performing one of the calculations. Are you dizzy now?

It is easy to see why quantum computing poses such a threat to modern encryption. Most encryption algorithms are based on "hard" computer science problems, like factoring large primes or solving certain discrete logarithm problems. These problems become significantly less difficult if you can perform the majority of the calculations simultaneously. However, for some time no one was really sure how to create a quantum computer, or precisely how one could be used to imperil current encryption standards. Peter Shor was instrumental in the latter effort. In 1994, Shor developed an algorithm that could be run by a quantum computer to factor a giant number, say a large prime. Shor's algorithm, run on a suitable quantum computer, could be used to break RSA. At the same time, Shor presented another algorithm that could be used by a quantum computer to solve discrete logarithm problems. Lov Grover's algorithm could similarly be used by a quantum computer to crack 3DES. We've handled 3DES for Grover with classical methods, but this does not lessen the threat that quantum cryptanalysis poses for modern encryption.

However, I will not go into quantum cryptanalysis or cryptography further here, as my intention with this series is to discuss post-quantum cryptography. What is the difference between quantum and post-quantum cryptography? I will discuss this as well as supersingular isogeny Diffie-Hellman in the next part to this series.

1: He performed a series of experiments to come to these conclusions, but we are simplifying. ↩
2: Fun fact: Deutsch was a believer of the many-worlds theory. ↩