Quantum computers promise advantages in solving computationally complex problems that today’s classical computers cannot solve. Up until now, classical computers—like the one you’re reading this on—have helped do just about everything in our daily lives, from connecting us to one another, doing our jobs, and playing games. But there are questions that would take them too long to answer—like “longer than the age of the universe” kind of too long.
Even a classical computer with as many transistors as there are atoms in the Milky Way still wouldn’t be up to the task of perfectly simulating a seemingly simple molecule. The problem is that bits, which are the basic building blocks of today’s computers, can’t accurately represent the complex interactions of the natural world. But because a quantum computer’s quantum bits (or “qubits”) mimic the quantum mechanics of nature, enough of them working together could simulate the chemistry of the real world, like a caffeine molecule. To put that in perspective, 300 qubits could represent more values than there are atoms in the observable universe.
Quantum computing has the potential for many other advances aside from simulating your morning joe. But it also has the potential to solve things that we don’t want solved—like breaking encryption.
Should we be worried about quantum computers?
Cryptography is based on difficult mathematical problems, such as factoring large numbers. It underpins everything we do electronically and provides the trust for all digital communication. However, quantum computers will likely be able to solve these classical equations in the time it takes you to make the aforementioned coffee.
Computer scientists and quantum physicists have therefore been thinking about using quantum mechanics for computation for decades. The two most important algorithms that have been created are Shor’s algorithm and Grover’s algorithm.
MIT professor Peter Shor published his factoring algorithm in 1994. Shor’s algorithm gave an exponential gain over the best known classical computational algorithms for the critical problems of integer factorization and discrete logarithms. Suddenly, these hard mathematical problems that are the basis of much of today’s public-key cryptography, used to secure software updates, authenticate users and systems, and validate the legitimacy of transactions, were at least theoretically underminable.
A second quantum algorithm, giving a quadratic advantage in database search, was created by renowned computer scientist Lov Grover in 1996. Grover’s algorithm could theoretically weaken the security of symmetric cryptographic algorithms, such as Advanced Encryption Standard (AES). AES has been adopted by the US government for bulk encryption tasks, such as enciphering major databases, file systems, and object storage to protect classified data. A large quantum computer running Grover’s algorithm could potentially crack these encryption systems.
Still, for many years the quantum threat to cryptography was considered theoretical. However, recent advances in building a physical quantum computer beg us to revisit how we secure our information.
Unfortunately, it’s a common misnomer to think that we can wait until a large quantum computer is built before changing the ways we do cryptography. But one cannot wait until a large enough quantum computer appears before starting to act, particularly if you have data that needs to remain confidential for years to come. Records of financial transactions and medical data need to be kept secure for decades, for example, meaning the systems that store them now need to be reinforced against future advances. There is also a serious risk that data harvested today could eventually be decrypted in the future by a quantum computer.
In addition, systems and technologies that we introduce today that we hope will exist well into the quantum future—like power plants, airplanes, and orbiting satellites—must be prepared for the pending quantum era; it’s a little annoying to bring a device orbiting the planet back down to earth to push quantum-safe updates. This means they need to be created with quantum-safe cryptographic schemes in mind. The story is the same for any new security frameworks, such as those being developed for smart city and transport infrastructures, blockchains, and e-governments.
What does quantum-safe cryptography look like?
The easiest example that gives you a taste of the kind of mathematical problems quantum-safe cryptography is based on is the famous knapsack problem. Suppose that you pick 1,000 random numbers of 1,000 digits each and then sum up a random subset of 500 of these numbers and publish the sum together with your original 1,000 numbers. The hard problem is for someone else to figure out which of the 500 numbers you used in the sum.
Interestingly, people tried to use this type of problem for cryptography back in the 1970s, when public-key cryptography was first invented. Unfortunately, they could not figure out how to do it right, and so the schemes that we use today, based on number theory problems, became the standards instead.
This problem actually has many applications outside of cryptography. For the past two decades, the knapsack problem has been one of the prime targets for researchers working on quantum algorithms as well. But there has been virtually no algorithmic progress in the area since the early 1980s. This is why the industry believes that this is a very good problem to use as a base for quantum-safe cryptography.
So what’s the hold up?
However, there is a major obstacle to using the above math to become quantum safe—the lack of cryptographic agility in both systems and applications.
Cryptography is often buried deep within systems and applications. It is complex and commonly bugged with implementation errors. This makes it difficult even to find the cryptography that needs replacing. We often find that applications and systems are adapted to the characteristics of the cryptography, which makes it complicated to change from one cryptographic scheme to another. This is akin to designing an electrical appliance to crucially depend on the shape of the socket it will be plugged into: It’s absurd, but this is the way cryptography is integrated today.
We only have to look at 2014 to see an example of why agility is important. The TLS Heartbleed vulnerability, which was estimated to cost the industry $500 million dollars, could have been prevented with a simple patch—if the integration of cryptography was more modular. So by addressing the issue of cryptographic agility, we can improve our cybersecurity posture at the same time as simplifying migration to quantum-safe schemes.
Why the time to act is now
The timeframe is still murky for when we might have a quantum computer powerful enough to run Shor’s and Grover’s algorithms. But when we do, it may be possible that anyone with access could be able to crack top-secret data. While significant progress toward this goal is being made, it’s still too early to circle a date on the calendar.
The good news is that quantum-safe cryptography works today. And the National Institute of Standards and Technology (NIST) is currently running a process to evaluate and standardize one or more quantum-resistant public-key technologies.
So what does all this mean for all of us who bank online or store our photos in the cloud? Simply put, it means we can rest easy knowing that a problem, which doesn’t exist yet, is already solved. How often can you say that about anything in life?