Will These Algorithms Save You From Quantum Threats?

In 1994, a Bell Labs mathematician named Peter Shor cooked up an algorithm with frightening potential. By vastly reducing the computing resources required to factor large numbers—to break them down into their multiples, like reducing 15 to 5 and 3—Shor’s algorithm threatened to upend many of our most popular methods of encryption.

Fortunately for the thousands of email providers, websites, and other secure services using factor-based encryption methods such as RSA or elliptic curve cryptography, the computer needed to run Shor’s algorithm didn’t exist yet.

Shor wrote it to run on quantum computers which, back in the mid-1990s, were largely theoretical devices that scientists hoped might one day outperform classical computers on a subset of complex problems.

In the decades since, huge strides have been made toward building practical quantum computers, and government and private researchers have been racing to develop new quantum-proof algorithms that will be resistant to the power of these new machines. For the last six years, the National Institute of Standards and Technology (NIST)—a division of the US Department of Commerce—has been running a competition to find the algorithms that it hopes will secure our data against quantum computers. This week, it published the results.

NIST has whittled hundreds of entries from all over the world to an initial list of just four: CRYSTALS-Kyber for general encryption, and CRYSTALS-Dilithium, FALCON, and SPHINCS+ for use in digital signatures during identity verification or when signing digital documents. “People have to understand the threat that quantum computers can pose to cryptography,” says Dustin Moody, who leads the post-quantum cryptography project at NIST. “We need to have new algorithms to replace the ones that are vulnerable, and the first step is to standardize them.”

Just as RSA encryption relies on the difficulty of factoring extremely large numbers, three of the four algorithms unveiled this week use a complicated mathematical problem that’s expected to be difficult for even quantum computers to wrestle with. Structured lattices are abstract multi-dimensional grids that are extremely challenging to navigate unless you know the shortcuts. In structured lattice cryptography, as with RSA, the sender of a message will encrypt the contents using the recipient’s public key, but only the receiver will have the keys to decrypt it. With RSA the keys are factors—two large prime numbers that are easy to multiply together but difficult to ascertain if you have to work backwards. In these post-quantum cryptography algorithms the keys are vectors, directions through the maze of a structured lattice.

Although it will be a few years before these standards are published in their final form, it’s a pretty big moment. “For the first time, we have something to use against a quantum threat,” says Ali El Kaafarani, the CEO of PQShield, which worked on the FALCON algorithm.

Those quantum threats might still be decades away, but security experts warn of “harvest now, decrypt later” attacks—bad actors hovering up caches of encrypted data with the expectation that they’ll eventually have a quantum computer that can access them. The longer it takes to implement quantum-proof cryptography, the more data will be vulnerable. (Although, Lancaster University quantum researcher Rob Young points out that a lot of sensitive data that could be harvested now is also time sensitive: Your credit card number today will be irrelevant in 15 years.)

“The first thing organizations need to do is understand where they are using crypto, how, and why,” says El Kaafarani. “Start assessing which parts of your system need to switch, and build a transition to post-quantum cryptography from the most vulnerable pieces.”

There is still a great degree of uncertainty around quantum computers. No one knows what they’ll be capable of or if it’ll even be possible to build them at scale. Quantum computers being built by the likes of Google and IBM are starting to outperform classical devices at specially designed tasks, but scaling them up is a difficult technological challenge and it will be many years before a quantum computer exists that can run Shor’s algorithm in any meaningful way. “The biggest problem is that we have to make an educated guess about the future capabilities of both classical and quantum computers,” says Young. “There’s no guarantee of security here.”

The complexity of these new algorithms makes it difficult to assess how well they’ll actually work in practice. “Assessing security is usually a cat-and-mouse game,” says Artur Ekert, a quantum physics professor at the University of Oxford and one of the pioneers of quantum computing. “Lattice based cryptography is very elegant from a mathematical perspective, but assessing its security is really hard.”

The researchers who developed these NIST-backed algorithms say they can effectively simulate how long it will take a quantum computer to solve a problem. “You don’t need a quantum computer to write a quantum program and know what its running time will be,” argues Vadim Lyubashevsky, an IBM researcher who contributed to the the CRYSTALS-Dilithium algorithm. But no one knows what new quantum algorithms might be cooked up by researchers in the future.

Indeed, one of the shortlisted NIST finalists—a structured lattice algorithm called Rainbow—was knocked out of the running when IBM researcher Ward Beullens published a paper entitled “Breaking Rainbow Takes a Weekend on a Laptop.” NIST’s announcements will focus the attention of code breakers on structured lattices, which could undermine the whole project, Young argues.

There is also, Ekert says, a careful balance between security and efficiency: In basic terms, if you make your encryption key longer, it will be more difficult to break, but it will also require more computing power. If post-quantum cryptography is rolled out as widely as RSA, that could mean a significant environmental impact.

Young accuses NIST of slightly “naive” thinking, while Ekert believes “a more detailed security analysis is needed”. There are only a handful of people in the world with the combined quantum and cryptography expertise required to conduct that analysis.

Over the next two years, NIST will publish draft standards, invite comments, and finalize the new forms of quantum-proof encryption, which it hopes will be adopted across the world. After that, based on previous implementations, Moody thinks it could be 10 to 15 years before companies implement them widely, but their data may be vulnerable now. “We have to start now,” says El Kaafarani. “That’s the only option we have if we want to protect our medical records, our intellectual property, or our personal information.”