There’s been a LOT of talk about how “quantum computing” will be the death of encryption as we know it. While most of this a just lot of hype, there is some truth to the possibility. And it seems that last week, Google may have reached an important milestone in this four decade old, yet still nascent technology. On a NASA owned website, a paper published, possibly by mistake, from a Google researchers claimed to have solved a very specific, ‘hard’ problem using a quantum processor; a problem that would take a traditional supercomputer about 10,000 years to calculate. Their quantum computer solved it in 200 seconds.
The Set Up
Google researchers cherry-picked a very specific problem that is both particularly hard for traditional computers, and particularly well suited for quantum computing. They used a 54 qubit quantum processor called ‘Sycamore’, specifically designed for this type of problem. The specific task was to mathematically prove the ‘randomness’ of sampled output from a quantum random number generator. They also ran the same challenge on powerful Google server clusters, and the Summit supercomputer at Oak Ridge National Laboratory.
It seems that in this competition, the traditional computers had the deck stacked against them. Still, the fact that a real quantum computer was able to do something in just over 2 minutes that would take us 10,000 years without them is a very strong proof-of-concept to say the least. At the minimum, it proves the feasibility of developing specialized quantum processors to solve very specific, mathematically hard problems.
Experts in the field (and competitors), such as IBM’s head of research Dario Gil, say that any such mention of quantum supremacy is just plain wrong. They indicate that the Sycamore processor was specifically built to perform this one task. While this may be true, consider how comparatively little time and effort it took to build this quantum computer versus running a traditional supercomputer for 10,000 years! Even if the future of quantum computers is one where myriad specialized processors are needed for different types of problems, supremacy over traditional computers could still be achieved. Traditional processors may still be used in general computing devices (smartphones, personal computers, etc.), while the large clusters of supercomputing monsters may be replaced by purpose-built quantum processors.
Traditional Encryption Dead?
The security of most traditional public key encryption techniques is premised on the fact that deciphering the key requires solving very hard mathematical problems such as large integer factorization or elliptic logarithm problems. With large enough key sizes, these problems take a traditional computer decades or longer to solve. Over the past few years, there’s been a lot of hype surrounding the implications that quantum computing will have. Large, stable quantum processors could solve these problems not in decades, but just seconds, using specialized quantum algorithms.
However, we are a long way away (many years if not decades) from even the most expensive, experimental quantum computers having the necessary size and stability to reach this breakthrough. Historically, cryptography has faced similar challenges to once-secure algorithms. The massive increase in computing speed over the last couple decades has basically killed the security offered by 512-bit RSA encryption, and by the MD5 signature algorithm. But as these vulnerabilities were created by an increase in CPU power, so was the solution to them. We simply increased the key size to 1024-bit, and now 2048-bit keys are standard, with 4096-bit keys commonplace as well. Importantly,doubling the key size here doesn’t simply double the difficulty: the problem becomes exponentially harder.
So we can just go on creating larger key sizes to prevent quantum computing attacks? Unfortunately, no. The real advantage of quantum computers is that the computing power also increases exponentially the more qubits you add. A completely new type of “quantum resistant” algorithm will be needed going forward to defend against quantum computers. The National Institute of Standards and Technology (NIST) is currently organizing an open competition to select the next generation of cryptographic algorithms that is resistant to cracking by quantum computers. (https://csrc.nist.gov/Projects/post-quantum-cryptography/news). What’s most interesting is that the peculiar properties of quantum mechanics that enable quantum computers may ALSO enable truly unbreakable ‘quantum encryption’. Here, a secret key could one day be transferred between parties using quantum methods such that if read or copied during transit, it would change the data and the recipient would know that the key had been modified or intercepted.
The future of cryptography will no doubt be drastically altered by the emergence of these quantum breakthroughs. But it will still take many more of these breakthroughs before it even becomes feasible for these processors to threaten any current strong cryptographic methods. We are already working on the next generation of algorithms to keep pace in a quantum world. Whatever the future holds, it is a strong bet that quantum mechanics will play a role in both cracking encryption, and securing it in the years to come.