How Quantum Computing Will Turn Digital Security Upside Down

You’ve probably heard some pretty grand claims about the power of quantum computers and how it will change our world. But there are a lot of misconceptions floating around. Before we focus on how quantum computing will effect digital security, let’s refresh our knowledge on what it actually is. I highly recommend you watch the following amazing explanation by Kurzgesagt:

Now we’re going to look at how our current security systems work and how quantum computing will effect them.

The Pillars of Digital Security

In cryptography, specifically public-key cryptography, many security models and encryption algorithms are built on two specific math problems that are difficult to solve: Integer Factorization and the Discrete Logarithm Problem.

• Integer factorization simply means turning a number N into two smaller numbers X and Y so that X * Y = N. For example, if I gave you the number 530453, you’d have to figure out that 530453= 581 * 913.

• The discrete logarithm problem has to do with modular exponentiation. Modular arithmetic deals with numbers in a certain range. If you go beyond that range, it wraps back around to zero and you resume from there. Let’s consider an example.

  Say we want to calculate (5*6) modulo 11, then 5 * 6 = 30, but after taking away as many 11s as you can (30-11-11), you end up with 8 instead.

  So, modular exponentiation uses exponentiation instead of multiplication. The discrete logarithm problem is when you’re given a number N, a base b, and a modulus M, you need to find the exponent e, such that b^e*mod M = N. For example, try solving 13^e mod 27 = 26.

There’s a few reasons why these two specific problems were picked to ensure the security of practically all public-key based systems, most notably SSL (HTTPS):

• There are no shortcuts for solving these problems. The easiest way to solve them is the same as the hardest way to solve them. Their best case and worst case complexities are bounded to the same degree.
• Bounded how? Exponentially. We can brute-force a solution to these problems pretty quickly for small numbers, so in cryptography we make sure these numbers are quite literally hundreds of digits long. The longer we make the numbers, the harder the above problems are to solve, the stronger the encryption is. As the numbers get larger, the problem becomes exponentially harder to solve.
• Another very important thing about these problems is that they’re extremely difficult to solve if you don’t know the answer, but once you have the answer it’s very easy to verify that it’s correct. It would take a handful of computer cycles for the device that you’re looking at right now to multiply two large numbers, even with hundreds of digits. But it would take a supercomputer thousands of years to figure out the opposite.

The largest RSA number ever factored was a measly 232 digits long and actually earned a prize of $200,000.

Enter Quantum Computing

You’d think that there are a lot of problems that fit the above criteria but there really aren’t. Almost all cryptography algorithms that are currently in use are based on variants of this problem. And it is this very problem that quantum computing can solve easily.

Quantum computing is a completely different beast. Certain things are possible using a quantum computer that just aren’t possible with regular computers. We can exploit these differences by using quantum algorithms. The algorithm that affects cryptography the most is Shor’s algorithm.

Shor’s algorithm doesn’t make solving integer factorization and the discrete logarithm problem instant, but it does make solving them much, much easier. How easier? The complexity goes from exponential to polynomial. This is huge.

When solving the above problems with N-digit numbers, it would take a regular computer 2^N steps but a quantum computer using Shor’s algorithm can solve it in N² steps instead. As an example:

• Say, for solving the above problem for a 10-digit number, a regular computer might take ~1024 (2¹⁰) steps but a quantum computer would only take 100 (10²) steps.
• For 30-digit numbers, a regular computer would take over a billion steps while a quantum computer would still only need a few hundred.

As the number of digits in N goes up, the difficulty difference between regular computers and quantum computers becomes even more extreme.

So this is where we stand with our current number-based cryptography. To make solving these problems harder we’ve been gradually ramping up the difficulty by using larger and larger numbers. For our current regular computers this makes solving cryptographic problems way harder, but for quantum computers it’s only a tiny bit harder.

We could make the numbers so massive that even using a quantum computer would be slow, but by then our regular computers would have a hard time just verifying the results. We’re talking numbers that may be hundreds of thousands, perhaps even millions of digits long and even as this problem will become too much for normal computers, we’ll have hardly slowed down a quantum computer.

The Silver Lining

So that’s that for public key cryptography, but what about other digital security systems?. Are all of our current systems hopelessly vulnerable to quantum computers? Thankfully, no. Quantum computers may be excellent at solving integer factorization and the discrete logarithm problem, but they’re still quite bad at attacking cryptographic hashes.

Hashes are a way of taking any amount of data, jumbling it around, then shrinking the result to a fixed-size string, a fingerprint. Just like our previous two problems, trying to solve what data went into making the fingerprint is exceptionally hard, but once you have the data, verifying that it matches the fingerprint is easy.

The process of trying to find the input that went into making a fingerprint is known as trying to find the hash’s pre-image. If it’s difficult to guess the hash’s input using only the output fingerprint then the hash is said to be pre-image resistant. This is part of what lead to the disastrous downfall of MD5.

Furthermore, the resulting fingerprints from a hash are not unique. Given the fact that a hashing algorithm takes any amount of data and reduces it to a much smaller fixed size, there are going to be multiple inputs which give the same fingerprint. Finding two different inputs which give the same result is known as a collision. If it’s difficult to find any two inputs which give the same result, the hash is said to be collision resistant.

If a hash function is both pre-image resistant and collision resistant, then quantum computers can’t solve it any easier than regular computers. And this gives us a way out: Replace our current quantum-vulnerable number-based cryptography with quantum-resistant hash-based cryptography. This is what needs to be done if we are to protect against the threat that quantum computers pose.

How long do we have?

The solution proposed above is our best bet to gradually modify current systems with ones that can resist a quantum attack. Let’s say we’re trying to break 2048-bit RSA keys (currently, one of the most common public key cryptography techniques). What exactly would it take to do this?

This is very much an area of active research and as such we don’t have any concrete answers. Following are the results of two separate research studies that attempt to answer this question:

• “If large quantum computers can be built, then RSA ciphers become useless. It is estimated that 2048-bit RSA keys could be broken on a quantum computer comprising 4,000 qubits and 100 million gates. Experts speculate that quantum computers of this size may be available within the next 20-30 years.” (Source)
• “Quantum memory units are called qubits and the largest quantum computers capable of running Shor’s algorithm only have about 20 qubits. (A Canadian company called DWAVE has a quantum computer with 512 qubits but it has very high error rates on its qubits and is based on another principle called quantum annealing.) To run Shor’s on 2048 bit RSA would require at least 10,000 qubits. It will probably be a while before such a machine can be built.” (Source)

So, the verdict is that we’re good for a few years. But quantum computing is growing faster than classical computing ever did. You can even buy a 2000 qubit computer right now at an affordable price of $15 million. Quantum computing will change digital security forever. The good news is we can probably handle it.

general , security