When quantum computers become powerful enough, they could theoretically crack the encryption algorithms that keep us safe. The race is on to find new ones.
By Tammy Xu September 14, 2022
Cryptographic algorithms are what keep us safe online, protecting our privacy and securing the transfer of information.
But many experts fear that quantum computers could one day break these algorithms, leaving us open to attack from hackers and fraudsters. And those quantum computers may be ready sooner than many people think.
That’s why there is serious work underway to design new types of algorithms that are resistant to even the most powerful quantum computer we can imagine.
What do these algorithms even do?
Cryptographic algorithms turn readable data into a secret, unreadable form so it can be safely shared on the open internet. They are used to secure all types of digital communication, like traffic on websites and the content of emails, and they are necessary for basic privacy, trust, and security on the web. There are several types of standard cryptographic algorithms widely used today, including symmetric-key and public-key algorithms.
Symmetric-key encryption is what people usually think of as encryption. It allows data and messages to be scrambled using a “key” so they are indecipherable to anyone without the key. It’s commonly used for securing sensitive data stored in databases or hard drives. Even data breaches that compromise databases full of sensitive user information aren’t as bad if the underlying data is encrypted—hackers may get the encrypted data, but there’s still no way to read it.
Public-key algorithms are important too. They help get around the fundamental drawback of symmetric-key encryption, which is that you need a secure way to share symmetric keys in the first place. Public-key algorithms use a set of two keys, one that is privately kept by the recipient and one that is made public.
Anyone can use the receiver’s public key to scramble data, which only the receiver can unscramble using the private key. This method can be used to transfer symmetric keys and can even be used in reverse for digital signatures—because private keys are unique to the receiver, receivers can use them to validate their identity.
Why do these algorithms need to be quantum resistant?
Cryptographic algorithms are able to keep data secret because they are mathematically intensive to break. It would take a modern computer trillions of years to break just one set of encryption keys using brute force.
But in the 1990s, before quantum computers were ever seriously talked about, mathematician Peter Shor discovered that the way a theoretical quantum computer would work happened to line up particularly well with cracking the kind of math used in public-key encryption.
Although no quantum computer existed at the time, other mathematicians were able to confirm that Shor’s Algorithm, as it became known, could theoretically be used by such computers to break public-key encryption. Now it’s widely accepted that once a working quantum computer with enough processing power is built, the algorithms we rely on today for public-key encryption will be easily breakable. The National Institute of Standards and Technology (NIST) predicts that quantum computers that can do this may be ready in just 10 to 20 years.
Luckily, symmetric-key encryption methods are not in danger because they work very differently and can be secured by simply increasing the size of the keys they use—that is, unless mathematicians can come up with a way for quantum computers to break those as well. But even increasing the key size can’t protect existing public-key encryption algorithms from quantum computers. New algorithms are needed.
What are the repercussions if quantum computers break encryption we currently use?
Yeah, it’s bad. If public-key encryption were suddenly broken without a replacement, digital security would be severely compromised. For example, websites use public-key encryption to maintain secure internet connections, so sending sensitive information through websites would no longer be safe. Cryptocurrencies also depend on public-key encryption to secure their underlying blockchain technology, so the data on their ledgers would no longer be trustworthy.
There is also concern that hackers and nation-states might be hoarding highly sensitive government or intelligence data—data they can’t currently decipher—in order to decrypt it later once quantum computers become available.
How is work on quantum-resistant algorithms progressing?
In the US, NIST has been looking for new algorithms that can withstand attacks from quantum computers. The agency started taking public submissions in 2016, and so far these have been narrowed down to four finalists and three backup algorithms. These new algorithms use techniques that can withstand attacks from quantum computers using Shor’s Algorithm.
Project lead Dustin Moody says NIST is on schedule to complete standardization of the four finalists in 2024, which involves creating guidelines to ensure that the new algorithms are used correctly and securely. Standardization of the remaining three algorithms is expected in 2028.
The work of vetting candidates for the new standard falls mostly to mathematicians and cryptographers from universities and research institutions. They submit proposals for post-quantum cryptographic schemes and look for ways to attack them, sharing their findings by publishing papers and building on each other’s different methods of attack.
In this way, they slowly weed out candidates that are successfully attacked or shown to have weaknesses in their algorithm. A similar process was used to create the standards we currently use for encryption.
However, there are no guarantees that a new type of clever quantum attack, or perhaps even conventional attack, won’t someday be discovered that can break these new algorithms.
“It’s impossible to prove that you can’t break it—the nonexistence of a mathematical algorithm is hard to impossible to prove,” says cryptographer Thomas Decru. But “if something stands the test of time in the world of cryptography, the trust grows.”
healthcarereimagined 