The race is on for quantum-safe cryptography
In 2016, Lily Chen started a competition to rewrite the building blocks of encryption.
With her team of mathematicians at the US National Institute of Standards and Technology, Chen reached out to academic and industry cryptographers around the world to find algorithms that could resist new threats posed by quantum computers. Five years later, the project is almost complete. After three rounds of elimination, Chen and her team have now narrowed the 69 submissions down to a final seven algorithms, with several winners to be named at the end of the year. If things go according to plan, the result will be a new set of NIST-certified algorithms — and a new measure of protection against the chaos of a fully operational quantum computer.
“Cryptosystems in devices and communication systems will not be secure anymore” when those computers reach their potential, Chen says. “It’s time to prepare for quantum threats.”
Chen has technical reasons to be concerned. Existing encryption systems rely on specific mathematical equations that classical computers aren’t very good at solving — but quantum computers may breeze through them. As a security researcher, Chen is particularly interested in quantum computing’s ability to solve two types of math problems: factoring large numbers and solving discrete logarithms (essentially solving the problem bx = a for x). Pretty much all internet security relies on this math to encrypt information or authenticate users in protocols such as Transport Layer Security. These math problems are simple to perform in one direction, but difficult in reverse, and thus ideal for a cryptographic scheme.
“From a classical computer’s point of view, these are hard problems,” says Chen. “However, they are not too hard for quantum computers.”
In 1994, the mathematician Peter Shor outlined in a paper how a future quantum computer could solve both the factoring and discrete logarithm problems, but engineers are still struggling to make quantum systems work in practice. While several companies like Google and IBM, along with startups such as IonQ and Xanadu, have built small prototypes, these devices cannot perform consistently, and they have not conclusively completed any useful task beyond what the best conventional computers can achieve. In 2019, Google reported that its quantum computer had solved a problem faster than the best existing supercomputers, but it was a contrived task with no practical application. And in 2020, academic researchers in China also reported their quantum computer had beat conventional computing in performing an algorithm that could offer utility for specialized optimization tasks. But so far, quantum computers have only managed to factor tiny numbers like 15 and 21 — a useful proof of principle, but far from a practical threat.
That hasn’t stopped researchers from trying to stay one step ahead of the quantum challenge. Peter Schwabe, a mathematician at the Max Planck Institute for Security and Privacy, has devised several cryptography schemes with colleagues that have beat the third round of NIST’s competition. One of his submissions qualifies as a lattice-based protocol, a class of quantum-resistant algorithms that involve a geometric puzzle in a grid of points, arranged across hundreds or even thousands of dimensions. To crack the code, the computer must use given line segments to solve the puzzle, such as finding the most compact way to connect the lines end to end in the grid.
“Lattice-based cryptography is, at the moment, considered the most realistic drop-in replacement for the protocols we have today,” says Schwabe.
It’s important to establish cryptographic standards now because once NIST standardizes a new cryptographic protocol, it will take years for some users to buy and set up the necessary technology. Another worry is that hackers today could intercept and store encrypted information, and then decrypt the messages a decade later with a quantum computer. This is a particular concern for government agencies that create documents intended to remain classified for years.
“We have to try and get these cryptosystems ready well in advance of quantum computers,” says NIST mathematician Dustin Moody, a member of Chen’s team.
In advance of NIST’s standards, some companies have already begun experimenting with these new cryptography schemes. In 2019, Google and the security company Cloudflare began testing the speed and security of two quantum computing-resistant protocols. “We hope that this experiment helps choose an algorithm with the best characteristics for the future of the internet,” wrote cryptographer Kris Kwiatkowski of Cloudflare in a blog post after the tests were performed.
When the winning algorithms are chosen, the hope is that NIST’s federal certification will spur more companies to follow suit, and give them a head start in testing and implementing quantum-safe cryptography. Ultimately, NIST researchers see this work as public service. They aim to make these cryptographic standards freely available. The agency doesn’t pay cryptographers to participate in the competition, and winners will not receive any money. “You just get fame in the cryptographic world, which carries its own weight,” says Moody.
And the winners get the satisfaction of knowing they’ve completely redesigned swaths of internet infrastructure. The new protocols will alter fundamental interactions on the internet, like how your computer confirms you’ve actually accessed the right website and not a hacker’s server — not to mention how companies encrypt your credit card number when you make an online purchase.
But the revolution will be quiet. “The average user is not really going to see or notice this,” says Moody. “Hopefully, it’ll all be done behind the scenes by the cryptographers and the people who put this into their products.” Like the best security products, you can tell it’s working when nobody notices the change.
In 2016, Lily Chen started a competition to rewrite the building blocks of encryption. With her team of mathematicians at the US National Institute of Standards and Technology, Chen reached out to academic and industry cryptographers around the world to find algorithms that could resist new threats posed by quantum…
