What Do Quantum Computers Mean for Security?

A Definition Of Quantum Computers

At the pace, technology has been growing over the last decades, our ability to make faster and smaller processors is slowing down. However, why do we have to make computers faster in the first place?

It doesn’t matter how fast the “classical” computers of today become; their architecture isn’t well-suited to solve certain kinds of problems, like drug research, training artificial intelligence, and breaking encryption algorithms.

Quantum computers aren’t the “faster horses” that Ford alluded to when he created the Model T, but rather an entirely different type of computer that changes the paradigms of how computers work, much like the car changed the transportation paradigm at the time.

They are another tool to aid researchers, scientists, and computer programmers in developing solutions that can radically alter how we interact with technology.

Quantum computers date way back to the 70s and 80s when quantum physicists were theorizing on how they could harness the quantum mechanics properties of particles and create a machine that could make use of them.

Feynman, a pioneer in the field, published a paper in 1982 titled Simulating Physics with Computers, where he said that to simulate quantum systems, we would need to build quantum computers.

And while quantum computers have been talked about for decades (you can take a look at the timeline), the first quantum computer was only ever built in 2009. The reason for such a delay is that they are extremely fickle and very sensitive to interference from the external world.

But now they are becoming increasingly mature, so we’re going to talk about how they work, what problems researchers are facing today, and their future.

“Are quantum computers the next big jump in technology advancement like classical computers were in the 1960s, and if they are, what does it mean for security?”

Tweet This

How Does Quantum Computing Work

As we’ve alluded to, the era of Silicon is coming to an end. We just don’t know when it’s gonna happen. (There has been some promising research suggesting that maybe using Graphene instead of Silicon to build microchips could allow the trend to continue, but it’s not yet clear how viable it is. It’s entirely possible that the curve could flatten in the next 10 years.)

The main issue preventing more growth with Silicon are fundamental problems of thermodynamics and quantum mechanics.

With the miniaturization of the transistor, it reaches a point where they’re so close to each other that the heat generated is so intense that the chip would melt. And on a sub-atomic level, the atoms are so close to each other that electron behavior becomes unpredictable. We simply don’t know where electrons are anymore: they could be inside the chip, outside of the chip... we just can’t know.

Now, even if Graphene-based chips, which have a much higher thermal and electrical conductivity than Silicon (meaning it can handle more heat and use less power), can continue the growth trend that started with Silicon, there will still be problems that will be impossible for classical computers to solve because of the way they operate.

Quantum computers promise to address the atomic limitations by exploring sub-atomic physical properties that weren’t even known to man 100 years ago and use insane amounts of parallelism to make computations.

Superposition

Classical computers perform operations using bits, which can be either 0 or 1. A quantum computer performs operations using qubits, or quantum bits, and they can be both 0 and 1 at the same time. They only collapse when we measure them.

The idea that one thing can be at two places at the same time or be two things at the same is a complicated idea to wrap your head around. There is no equivalent in the “real” world to describe this behavior, so scientists had to come up with a new term to describe it: superposition.

One way physicists try to interpret this is by saying that it’s as if the qubit exists in multiple parallel universes. The best explanation I’ve seen was from MIT professor Allan Adams: his full lecture is available for free on MIT OCW, so if you have an hour to spare, check that out. If not, the simplified version of multiple parallel universes will suffice for this article.

So, the idea is that if a qubit can be both 0 and 1 at the same time, as long as we don’t measure it, it could be doing many parallel computations at the same time.

With that in mind, we can use quantum gates to manipulate qubits. It accepts as inputs qubits in superposition, entangles them, manipulates probabilities according to what the program instructed it to do, and spits other qubits superposition as its output, which is then collapsed so we can measure the desired result.

Qubits assume a random discrete value when they collapse, and they could assume the form of the wrong answer. However, it’s possible to create quantum algorithms that would make bad answers cancel out and nudge the correct answer, so it’s more likely to appear as the result when the qubits are measured.

A quantum computer takes advantage of superposition by having qubits in superposition perform many different calculations at the same time, and only then making a measurement at the end of the computation where we retrieve the results that we are looking for.

Entanglement

If we only had to make individual qubits work, we’d already have reached a point where quantum computers could be commercially viable.

But what is desirable about quantum computing is the ability to make many computations in parallel, so the fact that we have to make them all work simultaneously is what makes this a hard problem.

When a group of quantum particles is generated in a way such that the state of each particle of the group can’t be described independently of the state of the others is what researchers call entanglement.

Entanglement is the other quantum propriety that makes quantum computers work. Changing the state of one entangled qubit will instantly change the state of the other qubit in a predictable manner.

This is what allows the power of quantum computers to grow much faster than classical computers: entangling additional qubits to a quantum computer produces an exponential increase in computing power.

Applications Of Quantum Computing

Harnessing the power of quantum mechanics will open a lot of new doors for problems that could be drastically sped up with increased parallelization.

Take drug research, for instance. The analysis of molecules for drug research and material science is a challenge today because calculating all of the quantum proprieties is very computationally expensive.

“It turns out it’s absolutely impossible to represent one simple little caffeine molecule in a classical computer,” says Bob Sutor, Vice President at IBM, in an interview with CNBC, “because the amount of information you would need to represent it, the number of zeros and ones you would need is around 10⁴⁸. The number of atoms on Earth is about 10 to 100 times that number. That’s never going to happen.”

The increased parallelization of quantum computers can help research solve this and other types of problems, including problems related to security, such as encryption.

Applications In Encryption

How quantum computing will affect encryption algorithms depends on the type of encryption. For example, let’s consider public encryption and RSA for a moment.

The security of RSA is based on the fact that finding a factor of a very, very big number is pretty much impossible.

The method we know for breaking encryption today is guessing which numbers could be the factors and see if it decrypts the data. If it isn’t, we try again, much like guessing the correct password by hashing several different possible passwords. But there are so many numbers to try that it would take millions of years to find using classical computers.

While we don’t know for sure if there’s an algorithm to expedite this process using classical computers, we know that there’s one algorithm for quantum computers that would take exponentially less time: Shor’s algorithm.

Shor’s algorithm is a quantum algorithm for finding factors of a number. Say you want to find factors for number N. The algorithm starts with a guess of what number could be a factor, but then it keeps optimizing the guess until it eventually guesses a number that does share a factor with N.

Now, you could run Shor’s algorithm on a classical computer, but it would be extremely slow. It’s the optimizing part of the algorithm that makes use of the quantum properties to factor numbers in a fraction of the time (in the order of weeks, days, and even hours).

For symmetric encryption, the story is a little bit different. In 1996, Lov Grover devised what is now known as Grover’s algorithm. It’s a searching quantum algorithm that finds a desirable output in just N^1/2 operations, where N is the sample size.

This means that a brute-force attack using Grover’s algorithm on a quantum computer could reduce the number of operations to brute-force a 128-bit AES key from 2¹²⁸ operations in the worst-case scenario to 2⁶⁴ operations, which is well within range.

However, symmetric encryption is very resistant to quantum computers because, basically, all Grover’s algorithm is doing is halving the key size, so we can just double the keyspace. Using Grover’s algorithm on AES-256 would require 2¹²⁸ operations, which is outside of range even for quantum computers in the conceivable future.

The Future Of Quantum Computing

In October 2019, Google published a paper suggesting it had achieved “quantum supremacy,” that is, that their quantum computer could perform a task in minutes that would take a classical supercomputer 10,000 years.

But IBM disputed their findings, saying that an ideal simulation of the same task could be performed in 2.5 days and with greater fidelity on a classical supercomputer.

They claimed the original meaning of the term “was to describe the point where quantum computers can do things that classical computers can’t, this threshold has not been met.”

Adding qubits and keeping them in a superposition state is the biggest engineering challenge for researchers, as any minor external disturbance can knock a qubit out of the delicate state of superposition. As a result, quantum computers have to be kept isolated from all forms of electrical interference and operate at temperatures to absolute zero – about 100 times colder than outer space.

The most qubits we have available today are around 50, and that’s incredibly powerful, especially if you consider the power grows exponentially with each additional qubit. But they also have really high error rates because of those problems with interference.

Shor and Grover’s algorithms need a quantum computer with millions of qubits to work. Will this computer exist? Not for at least a couple of decades, some experts say.

Even if we add more qubits faster than Moore’s Law pace, it still will take over 10 or 15 years to reach the point where we could realistically attempt to break encryption algorithms used today.

Hopefully, by the time quantum computers have matured, mathematicians and cryptographers will have created a quantum-resistant version of encryption algorithms.

And while quantum computers will not substitute classical computers – researchers and large businesses that need to solve complex problems will probably do so by accessing them remotely – they’re far from science fiction at this point.

“For those who are just getting started, they like to make noise about Sputnik and things like this. But let me give you some numbers,” says Sutor, “IBM has had quantum computers on the cloud since May of 2016. We’re not in any sort of Sputnik era. We’re not landing on the moon. But for those of you who like space history, I think we’re probably well into Mercury or Gemini.”