What are quantum-resistant algorithms—and why do we need them? – MIT Technology Review

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.
Tech Review Explains: Let our writers untangle the complex, messy world of technology to help you understand what's coming next. You can read more here.
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. 
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.
A multi-year hacking campaign shows how dangerous old flaws can linger for years.
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.
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.
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. 
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.
Quantum computing startups are all the rage, but it’s unclear if they’ll be able to produce anything of use in the near future.
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.”
The US has moved to restrict export of EDA software. What is it, and how will the move affect China?
General warming predictions are still on track, but recent heat waves are a stress test for the modeling of extreme events.
Three vaccines might help tackle the global outbreak. But can we rely on them—or even get hold of them?
Cryptocurrency hacks are increasing. Here’s how the government tries to track, freeze, and seize the stolen money before it disappears out of reach.
Discover special offers, top stories, upcoming events, and more.
Thank you for submitting your email!
It looks like something went wrong.
We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.
Our in-depth reporting reveals what’s going on now to prepare you for what’s coming next.
Subscribe to support our journalism.
© 2022 MIT Technology Review


Leave a Comment