Twenty-six innovative crypto algorithms have made the first cut in the effort to develop cryptographic standards that will be able to withstand quantum computers. The semifinalists will face at least a year of additional scrutiny by the National Institute of Standards and Technology and outside scientists.
“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.” If things progress smoothly, new standards could be available by 2023.
NIST’s Post-Quantum Cryptography Standardization project is a response to advances in quantum computing that threaten to make current cryptography obsolete in the not-too-distant future.
A new paradigm
Quantum computing takes advantage of the fact that subatomic particles can exist in multiple superimposed states at the same time, allowing them to carry more data than the binary digits—0 or 1—used in current digital computing. This science still is in its early stages, but a recent study by the National Academies of Sciences, Engineering and Medicine concluded that despite significant technical challenges, there is “no fundamental reason why a large, fault-tolerant quantum computer could not be built in principle.” This would have a major impact on today’s cryptography.
Concerns about this quantum threat are not new. It was shown in 1994 that quantum computers could break public key cryptographic functions, and since then the cryptographic community has been working on quantum-resistant cryptography.
In 2015 NIST held a workshop on “Cybersecurity in a Post-Quantum World,” which resulted in the multi-year effort to develop new crypto standards. A call for candidate algorithms that would be publicly vetted was issued in 2016.
A long road
NIST intends to select new standard algorithms for use in a variety of protocols, including Transport Layer Security (TLS), Secure Shell (SSH), Internet Key Exchange (IKE), Internet Protocol Security (IPsec), and Domain Name System Security Extensions (DNSSEC). Although practical quantum computers probably are a decade or more away, the time needed to identify and thoroughly test new workable cryptographic algorithms makes it prudent to begin the process now. The task is complicated by the fact that we do not know exactly how quantum computers will work and just what it will take for new algorithms to withstand them.
By November 2017 NIST had received 82 possible post-quantum algorithms, 69 of which met the minimum requirements for evaluation. NIST scientists spent the next year reviewing the candidates with the cryptography community, paring the list down to 26. Seventeen candidates are for public-key encryption and key establishment, and nine are for digital signatures.
Next steps
The program is not a winner-take-all contest. Multiple algorithms could be selected at the end of the process or none. The second round of evaluations is expected to take 12 to 18 months. NIST could propose new standards then or call for a third round.
The recent government shutdown, which included the Commerce Department and NIST, has had an impact on the program. Teams that submitted algorithms that made the first cut will have until March 15 to make tweaks to their candidates. “We originally planned that submission teams would have more time, however recent events out of our control have altered the timeline,” NIST said.
A second Post-Quantum Crypto Standardization Conference will be held in August in Santa Barbara, Cal., along with CRYPTO 2019.
Any new standard algorithms would not replace existing crypto standards, but would work alongside them. The goal of post-quantum cryptography is to develop cryptographic systems that are secure against both quantum and classical computers and can interoperate with existing protocols and networks.
The new public-key cryptography standards will specify one or more additional algorithms for digital signature, public-key encryption, and key-establishment, augmenting those standards now specified in FIPS 186-4, Digital Signature Standard (DSS); Special Publication 800-56A Revision 2, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography; and SP 800-56B, Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization.
You can find more details of the program at the NIST Post-Quantum Cryptography Web site.