The field has narrowed in the race to protect sensitive electronic information from the threat of quantum computers, which one day could render many of our current encryption methods obsolete.
As the latest step in its program to develop effective defenses, the National Institute of Standards and Technology (NIST) has winnowed the group of potential encryption tools—known as cryptographic algorithms—down to a bracket of 26. These algorithms are the ones NIST mathematicians and computer scientists consider to be the strongest candidates submitted to its Post-Quantum Cryptography Standardization project, whose goal is to create a set of standards for protecting electronic information from attack by the computers of both tomorrow and today.
“These 26 algorithms are the ones we are considering for potential standardization, and for the next 12 months we are requesting that the cryptography community focus on analyzing their performance,” said NIST mathematician Dustin Moody. “We want to get better data on how they will perform in the real world.”
Currently, the security of some cryptographic algorithms—which protect everything from online banking transactions to people’s online identities and private email messages—relies on the difficulty conventional computers have with factoring large numbers.
Quantum computers are still in their infancy, but their design—which draws upon very different scientific concepts than conventional computers—may eventually enable them to factor these large numbers relatively quickly, revealing our secrets. So post-quantum algorithms must be based on different mathematical tools that can resist both quantum and conventional attacks.
This winnowing of candidates advances NIST’s effort to develop these tools. After releasing a report on the status of quantum-resistant cryptography in April 2016, NIST followed up in December 2016 with a call to the public to submit post-quantum algorithms that potentially could resist a quantum computer’s onslaught. The agency spent one year collecting the submissions and another working with the larger cryptography community on a first round of review to focus on the most promising algorithms. Of the 69 submissions NIST received, these 26 algorithms made the cut.
This second round will focus more heavily on evaluating the submissions’ performance across a wide variety of systems, Moody said, because so many different devices will need effective encryption.
“We want to look at how these algorithms work not only in big computers and smartphones, but also in devices that have limited processor power,” he said. “Smart cards, tiny devices for use in the Internet of Things, and individual microchips all need protection too. We want quantum-resistant algorithms that can perform this sort of lightweight cryptography.”
In addition to considering the multitude of potential device types that could use the algorithms, the NIST team is focusing on a variety of approaches to protection. Because no one knows for sure what a working quantum computer’s capabilities will be, Moody said, the 26 candidates are a diverse bunch.
“A wide range of mathematical ideas are represented by these algorithms,” Moody said. “Most fall into three large families—lattice, code-based, multivariate—together with a few miscellaneous types. That’s to hedge against the possibility that if someone breaks one, we could still use another.”
The three families rely on different, promising sources of mathematical difficulty. Lattice cryptosystems are built using geometric structures known as lattices and are represented using mathematical arrays known as matrices. Code-based systems use error-correcting codes, which have been used in information security for decades. Multivariate systems depend on the difficulty of solving a system of quadratic polynomial equations over a finite field.
Once this second round of review is finished, it is possible there will be a third before NIST announces the post-quantum algorithms that will supplement or replace three standards considered to be most vulnerable to a quantum attack: FIPS 186-4 (which specifies how to use digital signatures), NIST SP 800-56A and NIST SP 800-56B (both of which specify how to establish the keys used in public-key cryptography). Factoring into this decision will be the state of quantum computer development as the months go by. Quantum computers may still be years away, said Moody’s colleague Gorjan Alagic, but many designers are focused on developing them.
“There’s no indication that the technological leap to a practical quantum computer will happen soon, but people are spending a lot of effort on it,” said Alagic, a mathematician and computer scientist at the University of Maryland and a NIST guest researcher. “It’s reasonable to assume it might happen faster, so we want to develop these algorithms quickly and responsibly.”
For more information, see the NIST Computer Security Resource Center’s announcement of the 26 candidates.
UPDATE (Jan. 31, 2019): Further details about the 26 candidate algorithms have now been published in NIST Internal Report (NISTIR) 8240, Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process.