The Quantum Threat to CryptographyBy
A dangerous tortoise-and-hare competition is currently being run between quantum computing and the classic cryptography that has secured the internet, blockchain ledgers, communication, and more. It doesn’t appear that the slowly developing quantum computing today will catch and defeat crypto soon, but the warning in the fable is appropriate.
Aesop’s waddling straggler had only his perseverance, but quantum computers have unbound potential and special talents—attack vectors like the Shor’s and Grover’s algorithms that can crack cryptography. The reason these two haven’t ended the race already is that what they do on conventional computers can take years to complete. But many expect that to change as quantum computers grow in scale and increase speeds.
Researchers have come up with a term for the moment when the tortoise will pass the hare. It’s Y2Q, the year when quantum code-cracking abilities will emerge as the final existential threat to classic cryptography. When this will happen is pure speculation, but whether it will happen has already been settled for many. In 2018, a report from the U.S. National Academies of Sciences, Engineering, and Medicine predicted that a powerful quantum computer applying Shor’s algorithm could crack a 1,024-bit implementation of the RSA (Rivest-Shamir-Adleman) encryption in fewer than 24 hours.
The mathematician responsible for one of the algorithms, Peter Shor, added his own warning in late 2020. “I think the only obstruction to replacing RSA [public-key cryptosystem] with a secure post-quantum cryptosystem will be willpower and programming time…. If we wait around too long, it will be too late.”
In late 2018, the editors of Nature magazine explained the risk for blockchain products: “Blockchain security relies on ‘one-way’ mathematical functions. These are straightforward to run on a conventional computer and difficult to calculate in reverse. For example, multiplying two large prime numbers is easy, but finding the prime factors of a given product is hard—it can take a conventional computer many years to solve.” (See “Quantum computers put blockchain security at risk.”)
But Shor’s algorithm is designed to be run on a quantum computer, and on a large-scale quantum computer it could take a number and output its factors in a fraction of the time. In mathematical terms, it would require polynomial rather than exponential amounts of time. Grover’s algorithm is also a quantum algorithm designed to speed searching in unsorted databases.
Today, RSA depends on the complexity introduced with large prime numbers. Nature predicts, “Within ten years, quantum computers will be able to calculate the one-way functions, including blockchains, that are used to secure the Internet and financial transactions. Widely deployed one-way encryption will instantly become obsolete.”
Writing in MIT Technology Review, Martin Giles warns, “Without ‘quantum-safe’ cryptographic defenses in place, all kinds of things, from autonomous vehicles to military hardware—not to mention online financial transactions and communications—could be targeted by hackers with access to quantum computers.” Add to that the crippling of the web protocol HTTPS that secures data sent on the internet, as well as any other personal information that today gets encrypted as a matter of course, and there will be a monumental disruption.
Adapting the strategy “If you can’t beat them, join them,” the race is now on to use the same quantum computing and perhaps even the power of a quantum internet to create new, more complicated encryption procedures. The goal is a post-quantum cryptography.
The Nature editors point out that the problem of “mass extinction of information security” isn’t a new one. The encryption created by the German military’s Enigma machines in World War II was ultimately hacked by the Allies, but that didn’t end encryption. And in 1977 the state-of-the-art Data Encryption Standard (DES) was broken in a public contest. A second contest to find a replacement protocol for the DES produced today’s Advanced Encryption Standard.
What requires special attention today is Shor’s warning about getting solutions done in time. As Giles explains, “The pressure is on because encryption technologies are deeply embedded in many different systems, so unraveling them and implementing new ones can take a great deal of time.”
Not everyone is predicting the race to be completed years from now. Roger Grimes, defense evangelist at the security awareness firm KnowBe4, announced at the end of last year, “[2021 will] likely see the first public acknowledgment of the quantum crypto break, where quantum computers are capable of breaking traditional public key crypto.”