What are quantum-resistant algorithms—and why do we need them?
Symmetric-key encryption is what people usually think of as encryption. It allows data and messages to become encrypted using a “key”, so that they are unreadable to anyone else. It is commonly used to secure sensitive data stored on hard drives or databases. Even data breaches that compromise databases containing sensitive user information are not as serious if the underlying data has been encrypted. Hackers may be able to access the encrypted data but it is impossible to read it.
Public-key algorithms are also important. These algorithms help to overcome the fundamental problem of symmetric-key encryption. You need a secure method to share symmetric keys. Public-key algorithms use two keys: one that is kept privately by the recipient and one which is made public.
Anyone can use the receiver’s public key to encrypt data. Only the receiver can decrypt the data using the private key. This can be used to transfer digital signatures and symmetric keys. Because private keys are unique to the receivers, receivers can use them for identity verification.
Why are these algorithms so quantum resistant? Cryptographic algorithm are mathematically difficult to break. They are therefore able to keep data secrets. To break one set of encryption keys by brute force, it would take a modern computer trillions years .
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. It is now widely accepted that the algorithms used for public-key encryption can be broken once a quantum computer with sufficient processing power has been built. 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. However, even increasing the key size won’t protect existing public keys encryption algorithms from quantum computers. We need new algorithms.
What are the consequences if quantum computers break encryption that we use?
Yeah, it’s bad. Digital security would be seriously compromised if public-key encryption was suddenly broken without a replacement. Websites use public-key encryption to protect their internet connections. Therefore, sensitive information sent through websites would be unsafe. Cryptocurrencies rely on public-key encryption to protect their underlying blockchain technology. Therefore, the data on their ledgers will no longer be trusted.
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 the work on quantum-resistant algorithms going? In the US, NIST is looking for new algorithms to withstand attacks by 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 are capable of surviving attacks by 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 to the new standard falls mainly on mathematicians, cryptographers, and researchers from universities and research institutes. They submit proposals for post quantum cryptographic schemes. They then look for ways to attack them.
In this way, they slowly weed out candidates that are successfully attacked or shown to have weaknesses in their algorithm. Similar processes were used to create encryption standards.
However, it is unlikely that a new, clever quantum attack or a conventional attack will be discovered that can break these new algorithms. It’s difficult to prove that you can’t crack it–the nonexistence a mathematical algorithm is hard-to-prove,” says Thomas Decru, cryptographer. But “if something stands the test of time in the world of cryptography, the trust grows.”
I’m a journalist who specializes in investigative reporting and writing. I have written for the New York Times and other publications.
