In 2016, Lily Chen started a competition to rewrite the building blocks of encryption.
With her team of mathematicians from the US National Institute of Standards and Technology, Chen has reached out to academic and industrial cryptographers around the world to find algorithms that can withstand new threats from quantum computing. Five years later, the project is nearing completion. After three rounds of elimination, Chen and her team have now narrowed the 69 entries down to the final seven algorithms, with several winners at the end of the year. If all goes according to plan, the result will be a new set of NIST-certified algorithms — and a new degree of protection from the chaos of a fully operational quantum computer.
“Cryptosystems in devices and communication systems will no longer be secure” when those computers reach their potential, Chen says. “It’s time to prepare for quantum threats.”
Chen has technical reasons to be concerned. Existing coding systems rely on specific mathematical equations that classical computers can’t solve very well, but quantum computers can blow through them. As a security researcher, Chen is particularly interested in quantum computing’s ability to solve two kinds of math problems: factoring large numbers and solving discrete logarithms (essentially solving the problem bx = a in front of X). Virtually all internet security relies on this math to encrypt information or authenticate users in protocols such as Transport Layer Security. These math problems are easy to perform in one direction but difficult in the reverse, making them ideal for a cryptographic scheme.
“From a classic computer’s point of view, these are difficult problems,” Chen says. “However, they are not too difficult for quantum computers.”
In 1994, 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 such as Google and IBM, along with startups such as IonQ and Xanadu, have built small prototypes, these devices cannot perform consistently and have failed to adequately complete any useful task beyond what the best conventional computers can accomplish. In 2019, Google reported that its quantum computer 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 that their quantum computer had beaten conventional computing by running an algorithm that could be useful for specialized optimization tasks. But so far, quantum computers have only managed to factor small numbers like 15 and 21 — a useful proof of principle, but far from a practical threat.
That doesn’t stop 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 who beat the third round of the NIST competition. One of his entries qualifies as a grid-based protocol, a class of quantum-resistant algorithms that comprise a geometric puzzle in a grid of dots arranged over hundreds or even thousands of dimensions. To crack the code, the computer has to use certain line segments to solve the puzzle, such as finding the most compact way to connect the lines from end to end in the grid.
“Grid-based cryptography is currently considered the most realistic replacement for the protocols we have today,” Schwabe says.
It is important to establish cryptographic standards now because once NIST standardizes a new cryptographic protocol, it will take years for some users to purchase and set up the necessary technology. Another concern is that hackers today can intercept and store encrypted information, then decrypt the messages a decade later with a quantum computer. This is a particular concern for government agencies that create documents that are intended to remain classified for years.
“We should try to get these cryptosystems ready well before quantum computers,” said NIST mathematician Dustin Moody, a member of Chen’s team.
Ahead of NIST’s standards, some companies have already begun experimenting with these new cryptography schemes. In 2019, Google and the security company Cloudflare testing speed and safety of two protocols that are resistant to quantum computers. “We hope this experiment will help choose an algorithm with the best features for the future of the internet,” Cloudflare cryptographer Kris Kwiatkowski wrote in a blog post after the tests were conducted.
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 deploying quantum secure cryptography. Ultimately, NIST researchers view this work as public service. They aim to make these cryptographic standards freely available. The agency does not pay cryptographers to enter the contest, and winners do not receive any money. “You just get fame in the cryptographic world, which has its own weight,” Moody says.
And the winners get the satisfaction of knowing that they have completely redesigned parts of the Internet infrastructure. The new protocols will change fundamental interactions on the Internet, such as how your computer confirms that you’ve actually visited the correct 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 won’t really see or notice this,” Moody says. “Hopefully it’s all done behind the scenes by the cryptographers and the people who put this in their products.” Like the best security products, you can see it working when no one notices the change.