Defending Against the Quantum Future
The U.S. government is racing to identify technologies that will resist the threat from quantum computers, which will render today’s encryption obsolete.
Recent breakthroughs indicate that the experimental technology could soon make the leap from the laboratory to the marketplace, explains Dustin Moody, mathematician and Post-Quantum Crypto project manager at the National Institute of Standards and Technology (NIST). “One of the impacts of quantum computers is that they would break some of the crypto systems that we use. Researchers in academia have been aware of it and thought about it, but it still seemed that quantum computers were quite a ways off,” Moody says. “There have been more advances in the engineering of quantum computers, so it could be within 10 to 15 years, possibly, that a quantum computer could be built.”
The standards NIST established for three types of encryption—digital signatures, public key encryption and public key establishment—will be jeopardized in a quantum world. In basic terms, a digital signature verifies a user’s identity. Moody compares it to a digital fingerprint. Public key encryption is used to scramble messages, and public key establishment is simply the process of generating an encryption key for a number of people to use. Ultimately, NIST could expand its search for cryptographic algorithms that serve other purposes, Moody indicates.
The Post-Quantum Crypto project attempts to establish encryption standards for a technology that has not yet materialized—a daunting task. “That’s one of the complexities we have to confront. It’s hard to know how a quantum computer will operate. People have designed algorithms that will be able to run on a quantum computer, but without the computer, we don’t know how fast it will be, how efficient it will be or how expensive it will be. We just have to do the best we can to predict these things,” Moody offers.
Furthermore, what researchers think they know about quantum technologies could easily change. “In the next year or two, we might get new information that will change the direction a little bit, so we have to be able to respond to that,” he says. “We tried to build that into our project here, and we’re letting people know upfront that we might change the rules or the goals or the evaluation criteria if there are new developments in the field as we go through this process.”
Time is of the essence. “The pressure we’re under means we can’t delay this effort much longer if we hope to finish it before quantum computers might be built,” Moody says.
The crypto project is part competition, part crowdsourcing. Anyone in the world can proffer solutions. NIST will winnow the submissions to a few that will be declared winners, and those will be published to generate public feedback. “We’ll be evaluating them internally, but we are definitely encouraging cryptographers and academics and industry worldwide to also evaluate and analyze these and write papers and publish their results and discuss [them],” Moody elaborates.
Late last year, NIST issued its call for proposals. Submissions are due by November 30. Evaluating them will take three to five years, and writing new standards could take another two years. The timeline “could change depending on how things go, but that’s our estimate at this point,” Moody states.
The agency is likely to select three algorithms to replace the ones at risk. That number may vary, however, depending on the solutions that emerge. “There might be a whole handful of winners at the end of this process,” Moody says.
Publishing the crypto algorithms in no way harms national security, he points out. The National Security Agency (NSA) and the Defense Department are responsible for classified crypto programs, but everything NIST does is unclassified. “The cryptography we use is such that everybody in the world can know the details of how it works and how it operates and how it implements. But when you use it correctly, an attacker still is not able to get your secrets out of it,” Moody declares.
In fact, posting the results of the NIST project functions as a kind of deterrent. “When we try to show that we have really good security with these algorithms, it is assumed that an attacker completely understands how these algorithms work,” he says.
Publishing the results also benefits anyone needing to rapidly swap encryption algorithms. “It’s useful for promoting crypto agility within a lot of the agencies and industry. That’s a useful property to have because you never know when some really smart person will come along and develop an attack that might weaken the security of the crypto system that you’re using,” Moody observes.
NIST will continue to study the solutions that do not make the cut. “It’s not the end of the story when we finish and announce the algorithms. Just because we don’t initially select an algorithm, it doesn’t mean that it’s out of the picture and lost,” he adds.
Post-quantum encryption research of this sort is still in its infancy, but it received a boost nearly two years ago, when the NSA announced its intent to transition to quantum-resistant cryptography. Several months later, NIST issued a report outlining the quantum computing threat, followed by its call for proposals.
For now, research centers on three types of post-quantum encryption: lattices, code-based cryptography and multivariant cryptography. Lattices are mathematical structures that can be represented in a number of ways, including matrices. Code-based cryptography, which has been used for decades, shows some signs of being quantum-resistant, and researchers are trying to buttress its weaknesses. “The main flaw is that [the algorithms] have giant key sizes compared to what we use today. It would be really difficult to use them in practice. Newer research has been looking at how to reduce the key sizes,” Moody notes.
The third major family, multivariant cryptography, uses quadratic equations similar to those in basic algebra in which x represents something unknown. In this case, however, the algorithms use many variables, not just one x. “It’s very efficient—very fast to use them,” Moody asserts.
If the public carries on as usual in a quantum future, NIST’s crypto project will have succeeded. “Hopefully, we get this all done in a way that the average user never has to worry about any of it. That’s the main goal,” Moody says.
