A society connected by a variety of devices: laptops, mobile phones, wearables, self-driving or self-flying things. We have standards for a common language that allows these devices to communicate with each other. This is critical for wide-scale deployment – especially in cryptography where the smallest detail has great importance.
Traditional computers work with binary digits, or bits as they are called for short, that are either zero or one.
Typically, zero and one are represented by some traditional physical property – a hole punched in a tape, or no hole; a metal disc magnetised one way or the other by an electric current; an electronic capacitor that holds a charge or not; and so on.
Quantum computers aren’t like that – they work with qubits, which can essentially represent zero or one at the same time.
In theory, that makes it possible to perform calculations in parallel that would normally require a loop to do them one at a time.
The qubits represent what quantum physicists would call a superposition of all possible answers, tangled together through the mystery of quantum mechanics.
The idea, loosely speaking, is that for some types of algorithm, a quantum computer can calculate in N units of time what would otherwise take 2N units of time to work out.
In other words, some problems that are conventionally considered to be exponential time algorithms would turn into polynomial time algorithms.
Exponents involve “raising something to the power of X”, and exponential functions grow enormously quickly.
Polynomials involve “multiplying X by something”, and even though polynomial functions can grow very fast, they’re much more manageable than exponentials.
Here’s a thought experiment: lay 40 sheets of office paper on top of each other to create a pile 40 times thicker than one sheet – about 4mm in total.
Now imagine taking the top sheet and folding it in half 40 times.
That many folds are impossible in practice, of course, but if you could do it, you’d end up with a piece of paper more than 100,000 kilometres thick.
Two more folds and you’d be further out than the moon.
As a result, many people are worried that quantum computers, if they really work as claimed and can be scaled up to have a lot more processing power and qubit memory than they do today, could successfully take on problems that we currently regard as “computationally unfeasible” to solve.
The most obvious example is cracking encryption.
If your security depends on the fact that a crook would need months or years to figure out your decryption keys, by which time he’d be too late, then you’re in trouble if someone finds a way to do it in seconds or minutes.
Here’s the difference between exponential time and polynomial time in measuring the cost of cracking codes.
Imagine that you have a cryptographic problem that takes 1,000,000 loops to solve today if you have a 20-bit key, but by doubling the key to 40 bits you square the effort needed, so that it now takes 1,000,000,000,000 loops. (Actually, 240, which is approximately a million million, or one trillion.)
Imagine that you can do 1000 loops a second: multiplying the key size by 2 just boosted the cracking time of your cryptosystem one million-fold, from 1000 seconds (under 20 minutes) to a billion seconds (more than 30 years).
Now imagine that a quantum computer’s cracking time doubled along with the keylength, instead of squaring – your added safety margin of 30 years just dropped back to an extra 20 minutes, so a key that you thought would keep your secrets for decades wouldn’t even last an hour.
In other words, if reliable quantum computers with a reasonable amount of memory ever become a reality – we don’t know whether that’s actually likely, or even possible, but some experts think it is – then anything encrypted with today’s strongest algorithms might suddenly become easy to crack.
Is this the end of the world as we know it, at least for cryptography?
Fortunately, the answer is, “No,” because there’s a catch.
If you loop through 256 possible solutions to a problem using a conventional algorithm and 16 of them are correct, you end up with a list of all 16 possibilities, thus reliably ruling out 240 of them.
From there, you can go on to dig further into the problem, knowing that you will eventually solve it because you’ll end up trying every valid path to the answer.
But with quantum computers, even though you can do a whole load of calculations in parallel because the qubits are in multiple quantum states at the same time, So if your quantum computer can do, say, 256 computations in parallel, you have to make sure that that there’s only one correct answer that can emerge before you go on to the next stage of the algorithm, or you might have discarded the path that leads to the right answer later on.
In other words, you might be able to “solve” each stage of a problem much faster than before, yet hardly ever get the correct answer, meaning that you’re stuck with repeating your “fast” calculations over and over again until you get lucky all the way through and end up at the genuine solution.
As a result of this stumbling block, not all encryption algorithms will be vulnerable to quantum cracking, even if a viable quantum computer is ever built.
Unfortunately, quantum computer calculations based on a process known as Shor’s algorithm just happen to provide super-quick solutions to various mathematical problems that we currently rely on heavily in modern cryptography.
Algorithms such as SHA-256 (used in hashing, for example to store passwords securely) and AES (used to encrypt files and hard disks securely) can’t be cracked with Shor’s algorithm.
But the algorithms that are widely used today for public key cryptography – the way we set up secure, authenticated web connections, for example – can be attacked quickly with a quantum computer.
When we encrypt data over a secure web connection, we usually use a non-quantum-crackable algorithm such as AES to keep the data secret, after agreeing on a random AES key first.
So far, so good, except that we use public key algorithms, such as RSA and elliptic curve cryptography (ECC), to do our initial AES key agreement, and those public-key algorithms can be attacked using Shor’s algorithm.
In other words, quantum computing can’t crack the AES encryption, but it doesn’t have to because it can crack the AES key instead, and then decrypt the AES data directly.
Some experts doubt that quantum computers can ever be made powerful enough to run Shor’s algorithm on real-world cryptographic keys.
They suggest that there’s an operational limit on quantum computers, baked into physics, that will eternally cap the maximum number of answers they can reliably calculate at the same time – and this upper bound on their parallel-processing capacity means they’ll only ever be any use for solving toy problems.
Others say, “It’s only a matter of time and money.”
Rather than simply bet that the first group are right, US standards body NIST is currently running a competition to design, analyse and choose a set of new algorithms for public key cryptography that are considered uncrackable even if a quantum supercomputer does get built.
The project is very much like previous crypto competitions that NIST has run, with a similar motivation.
In the 1990s, NIST ran a contest to select AES, needed to replace the no-longer-quite-safe-enough DES algorithm.
In the 2000s, the competitive target was SHA-3, a cryptographic hashing algorithm that was standardised just in case someone finds a way to crack SHA-256, and we need a trustworthy replacement in a hurry.
Quantum computers that can break meaningful cryptographic parameter settings do not exist, yet. They won't be built for at least the next few years.
