The quantum menace: Quantum computing and cryptography

Quantum computing continues to inhabit the nebulous space between practical application and theoretical speculation, but it is edging closer toward real-world use. One of the more interesting use cases for quantum computers is modern internet cryptography.

Quantum computing and qubits

Quantum computing‘s name comes from the fact that it relies on the properties of subatomic particles, governed by laws that seem strange to those of us rooted in the macro world. In particular, quantum computers use qubits (quantum bits) instead of the binary digits (bits) we know from traditional computer systems.

Qubits are probabilistic in nature, whereas bits are deterministic. A bit ultimately resolves down to a physical switch—albeit one that is very tiny, measured in a handful of nanometers. Bits are binary: either on or off, true or false, 0 or 1.

Not so with qubits.

A qubit’s physical basis can be numerous phenomena, like the spin of an electron or the polarization of photons. This is a fascinating topic: the realm of linear equations that bridge imagination and reality. Quantum mechanics is considered an interpretation of an underlying reality, rather than a description, and is home to intense computational complexity.

A qubit’s state is described as a linear superposition of the two possible states. Once observed, the state is resolved to true or false. However, the same input will not necessarily resolve to the same output, and the state when unobserved can only be described in probabilistic terms.

From a classical physics standpoint, what is even more astonishing is that qubits in a quantum computer can inhabit multiple states simultaneously. When a computer samples a qubit for its state, it resolves into a single either/or (known as a wave function collapse).

Quantum computing in cryptography

All of this is rather interesting from a scientific and philosophical standpoint. For example, the functionality of quantum computers verifies the effect of observation on particles and suggests that, indeed, God does play dice with the universe. But here, we are concerned with the practical aspects of quantum computing’s increasing capacity on our everyday lives. In the coming years, the most profound impact will likely be in cryptography.

The best-known avenue from quantum computing to cryptography is a theoretical breakthrough that occurred in 1994: Shor’s algorithm. In theory, this algorithm showed the capacity of a quantum Turing machine to efficiently solve a class of problems that were intractable using traditional computers: the factoring of large integers.

If you are familiar with asymmetric cryptosystem algorithms like Diffie-Hellman and RSA, you know that they rely on the difficulty of solving factors for large numbers. But what happens if quantum computing solves that?

Cracking large integers with quantum mechanics

Shor’s algorithm and a handful of other algorithms leverage quantum mechanics to crack the one-way functions at the heart of asymmetric cryptography. The Adiabatic quantum computation has also been used to attack factorization.

Shor’s and other algorithms count on the quantum computer’s ability to inhabit a multitude of states by virtue of qubits. They then sample those qubits (which collapses their state) in a way that allows for a high degree of probability in the sampling. Essentially, we hand off the question of “What are the factors for a given number” to the mysterious world of the unseen, where the particle properties can exist in multiple states. Then, we query those properties for the most probable answer.  (Yes, this actually works.)

The largest number yet factored by Shor’s algorithm is 21. The Adiabatic quantum computation has successfully factored 143.

These algorithms are sophisticated and impressive, but so far, their numbers are paltry. The current standard for RSA is 2048 bits, which is 617 digits! However, while attacking the number 143, researchers unknowingly revealed an approach that allows larger numbers, at least in theory. One example is 56,153, which is still a relatively small number compared to what would be required to compromise real-world cryptosystems. It also depends on a reductive trick that can’t be used for all numbers.

The threat to web security infrastructure

What we know for now is that fundamental aspects of the quantum attack on asymmetric algorithms are being ironed out. How fast will the technology advance to the point where it can approach significantly larger numbers?

Interestingly, the symmetric algorithms we use every day (like AES) are not terribly vulnerable to quantum algorithms. Grover’s algorithm is the one that applies. It is unable, even in theory, to reduce the time needed to attack these algorithms much further than classic algorithms, provided 256-bit keys are used.

Most symmetrical secured communication, however, establishes its keys via asymmetric exchange. So, most web traffic today is vulnerable to advanced quantum computing attacks. If an attacker can discover the key established at the outset of an interaction, no amount of symmetric encryption will be of use.

So the threat to web security infrastructure is real. Let’s think a moment about the dynamics at play. The first things to consider are sheer economics and access. Right now, only organizations awash in cash can afford to tinker with such things. IBM, Google, and research scientists in China are vying for leadership in producing viable systems, along with a host of university efforts. Behind the scenes, government agencies like the US National Security Agency are surely not idle. In fact, NSA has its own take on the issue of public cryptography and quantum computing.

Evolving security for quantum computing

It’s unlikely that small scale actors will achieve quantum computing capabilities sufficient to attack modern asymmetric keys until long after large institutions have done it. That means we are in a long period of time where security infrastructure can evolve responsively to the dynamics of quantum computing.

No one knows when truly crypto-menacing quantum machines will emerge, but it seems likely that it will happen. Two yardsticks for getting a handle on the question are the number of qubits in a system and the longevity of those qubits.

Qubits are subject to what is called decoherence. Entropy is always whisking away the delicate ensembles of electrons and photons. The trouble is that both the number and longevity of qubits are tough to quantify. How many qubits are needed for a practical reproducible attack on an RSA 2048 key? Some say dozens, some say millions. How much coherence is required? Some say hundreds of nanoseconds, some say minutes. 

And all of this can be upended by techniques like the aforementioned tricky use of pre-processing algorithms. Who knows what ingenious undergraduate is right now thinking up a new approach. The people who factored 143 on a quantum machine didn’t even realize they had also cracked 56,153 until two years later.

Post-quantum cryptography

All roads lead to a post-quantum world, and many people are already hard at work on it. The US National Institute of Standards and Technology is hosting competitions for developing quantum-resistant algorithms right now. Some of these efforts are netting results.

In the final analysis, we can say the quantum menace to cryptography is real, based on increasingly more real-world results. But for now, it’s more than counterbalanced by countervailing forces. We may eventually have to say goodbye to some of our old beloved algorithms, but new ones will take their place.

It will be an interesting dance to watch over the next decade.