New technologies could stand before the power of quantum computers – if we apply them in time
In 2016, Lily Chen launched a competition to rewrite the building blocks of encryption.
Along with his 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 the new threats posed by quantum computers. Five years later, the project is almost complete. After three rounds of elimination, Chen and his team have now narrowed down the 69 submissions to the final seven algorithms, with multiple 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 device 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 encryption systems rely on specific mathematical equations that classical computers are not very good at solving – but quantum computers can wind 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 problem solving). bx = a For x). A lot of 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 the opposite, and are thus ideal for a cryptographic scheme.
“From a classical computer standpoint, these are difficult problems,” Chen says. “However, they are not too hard for a quantum computer.”
In 1994, mathematician Peter Shor described in a paper how a future quantum computer could solve both factoring and discrete logarithms problems, but engineers still struggled to put quantum systems into practice. While many companies like Google and IBM have built small prototypes with startups like IonQ and Xanadu, these devices may not perform consistently, and they haven’t conclusively accomplished any of the useful functions that the best traditional computers can achieve. can. In 2019, Google reported that its quantum computer had solved a problem faster than the best existing supercomputers, but it was an accidental task with no practical application. And in 2020, academic researchers in China also reported that their quantum computer beat conventional computing in performing an algorithm that could provide utility 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 danger.
That hasn’t stopped researchers from trying to stay one step ahead of the quantum challenge. Mathematician Peter Schwabe of the Max Planck Institute for Security and Privacy, along with collaborators, has devised several cryptography schemes that beat NIST’s third round of competition. One of their submissions qualifies as lattice-based protocols, a class of quantum-resistant algorithms that involve a geometric puzzle in a grid of points arranged in hundreds or thousands of dimensions. To crack the code, the computer must use a given line segment to solve a puzzle, such as finding the most compact way to connect the lines end-to-end in a grid.
“Lattice-based cryptography is, at this time, considered the most realistic drop-in replacement for the protocols we have today,” says Schwabe.
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 install the required technology. Another concern is that hackers today can intercept and store encrypted information, and then a decade later decrypt the messages with a quantum computer. This is of particular concern to government agencies that create documents intended to remain classified for years.
“We need to try to design these crypto systems well before quantum computers,” says NIST mathematician Dustin Moody, a member of Chen’s team.
Prior to NIST’s standards, some companies began to experiment with these new cryptography schemes. In 2019, Google and security company Cloudflare started speed and safety test Two quantum computing-resistant protocols. “We hope this experiment helps to choose an algorithm with the best features for the future of the Internet,” Cloudflare cryptographer Chris Kwiatkowski wrote in a blog post after the tests were conducted.
When the winning algorithm is chosen, the hope is that NIST’s federal certification will inspire more companies to follow suit, and give them a head start in testing and implementing quantum-secure cryptography. Ultimately, NIST researchers view this work as a public service. They aim to make these cryptographic standards freely available. The agency does not pay cryptographers to participate in the contest, and the winners will not receive any money. “You get fame in the cryptographic world, which carries its own weight,” Moody says.
And the winners get the satisfaction of knowing that they have completely redesigned the internet infrastructure. The new protocols will change fundamental interactions on the Internet, such as how your computer verifies that you have indeed accessed the correct website and not a hacker’s server – not to mention that companies check when you shop online. How do you encrypt your credit card number?
But the revolution will be quiet. “The average user isn’t really going to see or notice this,” Moody says. “Hopefully, all of this will be done behind the scenes by cryptographers and the people who put it into their products.” Like the best security products, you can tell it’s working when no one notices the change.