Quantum computers — exotic machines capable of solving practical problems that would thwart any conventional supercomputer — remain years or decades away. However, yesterday the administration of President Joe Biden took a step to anticipate the possible deployment of such machines. In a new national security memorandum, the White House asks federal agencies to prepare to transition from encryption algorithms used today to secure communications on the Internet and other networks to new algorithms resistant to attacks from a quantum computer.
The memo envisions the change starting in 2024, when the first standard for such “post-quantum cryptography” is expected to emerge, and to be completed before 2035. Fortunately for internet companies, such post-quantum cryptography will involve changes primarily in the software. “You don’t need a quantum computer to implement these post-quantum solutions,” says Dustin Moody, a mathematician at the National Institute of Standards and Technology (NIST). Still, he says, “The transition is expected to be quite difficult, as with any crypto transition we’ve made.”
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 mechanics quantum, 0 and 1 at the same time. Such bidirectional states at once allow a quantum computer to encode all possible solutions to some problem as abstract quantum waves. Set things up and, in the bowels of the machine, the waves will interfere so that the bad solutions cancel each other out and the good solution emerges.
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 over the Internet or other network. Often the public key algorithm is only used to communicate another key, a secret key which two correspondents – say Alice and Bob – use to initialize a second separate encryption program which they use in parallel to encode and decode the most of their message. Yet if an indiscreet person – say Eve – can hack into the public key system, they can steal the secret key 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 of which are prime numbers. If Alice wishes to receive a secret message from Bob, she sends him the key and he uses it to scramble her digital message according to a complicated and publicly known algorithm. But it is very difficult for Eve to undo the algorithm unless she knows the prime number factors of the key. Alice keeps these factors as her private key, allowing her to quickly decrypt Bob’s message. However, a quantum computer would be able to factor the huge number much faster than a regular computer, also allowing Eve to decipher the message in a jiffy.
Given the looming threat, mathematicians and cryptographers are already working on alternative public-key encryption schemes that are resistant to quantum computer hacking. For example, in one approach, the public key consists of a set of vectors that can be added to create a regular array of points called an array in multi-dimensional space. Using vectors, Bob encodes his message as a point close to one in the network. Eve will have a hard time figuring out the exact mathematical combination of the vectors Bob used, which make up his message. But Alice can find the combination because she has a simpler, but equivalent set of vectors as her secret key with which to attack the problem.
Since 2017, NIST has been working with researchers to develop standards for post-quantum cryptography algorithms, such as the size of the public key. In a few weeks, the agency will announce the handful of winning algorithms for which it will codify standards, Moody says. This should put NIST on track to announce these standards by 2024. The memo also calls on NIST to form a project within 90 days “to work with the private sector to address the 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 imperceptible. However, for the algorithms to work effectively, microchip makers will need to modify their designs, says Lily Chen, a mathematician at NIST. As a result, how quickly new algorithms take hold will largely depend on the decisions of manufacturers and equipment suppliers, Chen said. “At some point I will have 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 that a quantum computer can never crack the new algorithms, there is no ironclad proof. But that’s nothing new, Moody notes, because there’s also no evidence that a conventional supercomputer can crack today’s public-key algorithms.