The race to save the Internet from quantum hackers
(Nature) In cybersecurity circles, they call it Q-day: the day when quantum computers will break the Internet. Davide Castelvecchi has written an extensive review explaining the need to protect online communications from quantum computers that could crack current encryption. Castelvecchi also provides an extensive review of current efforts to thwart future data thieves. Inside Quantum Technology has summarized below, but the complete article is well worth the time to read.
Almost everything we do online is made possible by the quiet, relentless hum of cryptographic algorithms. But machines that will exploit the quirks of quantum physics threaten that entire deal. If they reach their full scale, quantum computers would crack current encryption algorithms exponentially faster than even the best non-quantum machines can. “A real quantum computer would be extremely dangerous,” says Eric Rescorla, chief technology officer of the Firefox browser team at Mozilla in San Francisco, California.
The machines that don’t yet exist endanger not only our future communications, but also our current and past ones. Data thieves who eavesdrop on Internet traffic could already be accumulating encrypted data, which they could unlock once quantum computers become available, potentially viewing everything from our medical histories to our old banking records.
The risk is real enough that the Internet is being readied for a makeover, to limit the damage if Q-day happens. That means switching to stronger cryptographic systems, or cryptosystems. Fortunately, decades of research in theoretical computer science has turned up plenty of candidates. These post-quantum algorithms seem impervious to attack: even using mathematical approaches that take quantum computing into account, programmers have not yet found ways to defeat them in a reasonable time.
Which of these algorithms will become standard could depend in large part on a decision soon to be announced by the US National Institute of Standards and Technology (NIST) in Gaithersburg, Maryland.
That will be only the beginning of a long process of updating the world’s cryptosystems — a change that will affect every aspect of our lives online, although the hope is that it will be invisible to the average Internet user. Experience shows that it could be a bumpy road: early tests by firms such as Google haven’t all run smoothly.
“I think it’s something we know how to do; it’s just not clear that we’ll do it in time,” Peter Shor, a mathematician at the Massachusetts Institute of Technology in Cambridge whose work showed the vulnerabilities of present-day encryption, told Nature in 2020.
Even if Q-day never happens, the possibility of code-breaking quantum machines has already changed computer science — and, in particular, the ancient art of cryptography. “Most people I know think in terms of quantum-resistant crypto,” says computer scientist Shafi Goldwasser, director of the Simons Institute for the Theory of Computing at the University of California, Berkeley.
The majority of the algorithms that made it to NIST’s final roster rely, directly or indirectly, on a branch of cryptography that was developed in the 1990s from the mathematics of lattices.
In 2015, the NSA’s unusually candid admission that quantum computers were a serious risk to privacy made people in policy circles pay attention to the threat of Q-day. “NSA doesn’t often talk about crypto publicly, so people noticed,” said NIST mathematician Dustin Moody in a talk at a cryptography conference last year.
Under Moody’s lead, NIST had already been working on the contest that it announced in 2016, in which it invited computer scientists to submit candidate post-quantum algorithms for public-key cryptography, releasing them for scrutiny by the research community.
Teams from academic laboratories and companies, with members from four dozen countries on six continents, submitted 82 algorithms, of which 65 were accepted.
Although NIST is a US government agency, the broader crypto community has been pitching in. “It is a worldwide effort,” says Philip Lafrance, a mathematician at computer-security firm ISARA Corporation in Waterloo, Canada.
China is said to be planning its own selection process, to be managed by the Office of State Commercial Cryptography Administration (the agency did not respond to Nature’s request for comment).
If all goes to plan, the Internet will be well into its post-quantum era by the time computing enters its quantum era. This post-quantum Internet could some day be followed, confusingly, by a quantum Internet — meaning a network that uses the principles of quantum physics to make information exchange hacker-proof.
But that is no reason to be complacent. Fully transitioning all technology to be quantum resistant will take a minimum of five years, Rescorla says, and whenever Q-day happens, there are likely to be gadgets hidden somewhere that will still be vulnerable, he says. “Even if we were to do the best we possibly can, a real quantum computer will be incredibly disruptive.”