Quantum computers—exotic machines that can solve practical problems that would stymie any conventional supercomputer—remain years or decades away. However, yesterday President Joe Biden’s administration took a step to anticipate the eventual deployment of such machines. In a new national security memorandum, the White House instructs federal agencies to prepare to shift from the encryption algorithms used today to secure communications on the internet and other networks to new algorithms resistant to attack by a quantum computer.
The memo envisions the shift beginning in 2024, when the first standard for such “post-quantum cryptography” should emerge, and being complete before 2035. Fortunately for internet companies, such post-quantum cryptography will involve changes mostly in software. “You don’t need a quantum computer to implement these post-quantum solutions,” says Dustin Moody, a mathematician with the National Institute of Standards and Technology (NIST). Still, he says, “the transition should be quite challenging, as with any crypto transition that we’ve done.”
Whereas a conventional computer processes information by flipping bits that can be set to 0 or 1, a quantum computer manipulates quantum bits or qubits that can be set to 0, 1, or, thanks to the weird rules of quantum mechanics, 0 and 1 at the same time. Such two-ways-at-once states enable a quantum computer to encode all possible solutions to certain problems as abstract quantum waves. Set things up right and, in the guts of the machine, the waves will interfere so that the incorrect solutions cancel one another, and the right solution pops out.
Since 1994, scientists have known that, in principle, a quantum computer should be able to crack so-called public-key encryption schemes. For the sake of efficiency, such schemes are typically used to initiate private communications on the internet or some other network. Often, the public-key algorithm serves only to communicate another key, a secret one that two correspondents—say, Alice and Bob—use to initialize a second separate encryption program that they use in parallel to encode and decode the bulk of their message. Still, if an eavesdropper—say, Eve—can hack the public-key system, she can steal the secret one and decode the entire exchange.
In current public-key systems, the public key is a gigantic number that is the product of two factors, both prime numbers. If Alice wishes to receive a secret message from Bob, she sends him the key and he uses it to scramble his numerical message according to a complicated algorithm that’s publicly known. But it’s very difficult for Eve to undo the algorithm unless she knows the key’s prime-number factors. Alice keeps those factors as her private key, which enables her to quickly unscramble Bob’s message. However, a quantum computer would be able to factor the huge number much faster than an ordinary computer, enabling Eve to unscramble the message in a jiffy, too.
Given the looming threat, mathematicians and cryptographers are already working on other public-key encryption schemes that are resistant to hacking by quantum computer. For example, in one approach, the public key consists of a set of vectors that can be added together to create a regular array of points called a lattice in a many-dimensional space. Using the vectors, Bob encodes his message as a point near one within the lattice. Eve will struggle to determine the exact mathematical combination of vectors that Bob used, which constitute his message. But Alice can figure the combination out because she possesses as her secret key a set of simpler, but equivalent, vectors with which to attack the problem.
Since 2017, NIST has been working with researchers to develop standards for post-quantum cryptography algorithms, such as how big the public key must be. Within weeks, the agency will announce the handful of winning algorithms for which it will codify standards, Moody says. That should put NIST on track to announce those standards by 2024. The memo also calls on NIST to form within 90 days a project “to work with the private sector to address cybersecurity challenges posed by the transition to quantum-resistant cryptography.” That work is already underway, Moody says.
For the average person, the transition to post-quantum cryptography should be largely unnoticeable. However, to make the algorithms run efficiently, microchip manufacturers will have to tweak their designs, says Lily Chen, a mathematician at NIST. As a result, exactly how quickly the new algorithms take hold will depend in large measure on the decisions of equipment manufacturers and vendors, Chen says. “At some point, I will get a new smartphone,” she says, “but whether the smartphone will use post-quantum cryptography will be the vendor’s decision.”
Curiously, although there are strong arguments suggesting a quantum computer can never crack the new algorithms, there’s no ironclad proof. But that’s nothing new, Moody notes, as there is also no proof that a conventional supercomputer can crack the current public-key algorithms.