If an exotic quantum computer is invented that could break the codes we depend on to protect confidential electronic information, what will we do to maintain our security and privacy? That's the overarching question posed by a new report from the National Institute of Standards and Technology (NIST), whose cryptography specialists are beginning the long journey toward effective answers.
NIST Internal Report (NISTIR) 8105: Report on Post-Quantum Cryptography details the status of research into quantum computers, which would exploit the often counterintuitive world of quantum physics to solve problems that are intractable for conventional computers. If such devices are ever built, they will be able to defeat many of our modern cryptographic systems, such as the computer algorithms used to protect online bank transactions. NISTIR 8105 outlines a long-term approach for avoiding this vulnerability before it arises.
"There has been a lot of research into quantum computers in recent years, and everyone from major computer companies to the government want their cryptographic algorithms to be what we call 'quantum resistant,'" said NIST mathematician Dustin Moody. "So if and when someone does build a large-scale quantum computer, we want to have algorithms in place that it can't crack."
The report shares NIST's current understanding of the status of quantum-resistant cryptography, and details what the agency is doing to mitigate risk in the future. One overall recommendation for the near term is that organizations focus on "crypto agility," or the rapid ability to switch out whatever algorithms they are using for new ones that are safer.
Creating those newer, safer algorithms is the longer-term goal, Moody says. A key part of this effort will be an open collaboration with the public, which will be invited to devise and vet cryptographic methods that—to the best of experts' knowledge—will be resistant to quantum attack. NIST plans to launch this collaboration formally sometime in the next few months, but in general, Moody says it will resemble past competitions such as the one for developing the SHA-3 hash algorithm, used in part for authenticating digital messages.
"It will be a long process involving public vetting of quantum-resistant algorithms," Moody said. "And we're not expecting to have just one winner. There are several systems in use that could be broken by a quantum computer—public-key encryption and digital signatures, to take two examples—and we will need different solutions for each of those systems."
Many current algorithms rely on the difficulty that conventional computers have with factoring very large numbers, a difficulty that a quantum computer can overcome. Defenses that rely on different mathematical approaches might stymie a quantum computer, and there is worldwide research interest in developing them.
While no one has yet come close to building a quantum computer that could threaten the systems we currently use, Moody says it is important to think about the future before it arrives, as it will take years to vet the candidates.
"Historically, it has taken a long time from deciding a cryptographic system is good until we actually get it out there as a disseminated standard in products on the market. It can take 10 to 20 years," he said. "Companies have to respond to all the changes. So we feel it's important to start moving on this now."