NIST Round Two: One Step Closer to Standardization

By Filip Pawlega, Security Researcher, ISARA Corporation
Published on February 26, 2019

Best practices for cryptography evolve with time, and staying secure sometimes requires immediate reaction. The transition to Elliptic Curve Cryptography specified by the US National Security Agency’s 2005 “Suite B” recommendation included a comfortable transition period. However, in August 2015, the NSA unexpectedly publicized a report recommending that any institutions which had still not completed the transition to Suite B schemes should continue using the older schemes and instead prepare for an upcoming transition to quantum-safe cryptography.

Soon after, in 2016, the US National Institute of Standards and Technology (NIST) – whose cryptographic standards are followed internationally – announced a call for proposals for quantum-safe (or “post-quantum”) cryptographic schemes. Since then quantum technologies have become much more visible in the media, and heavily funded in government projects around the world.

The NIST submission window closed on November 30, 2017 with 69 post-quantum algorithm candidates accepted. On January 30th, 2019 NIST made their first major announcement about the selection process, revealing that only 26 schemes will remain in consideration for the next round of the standardization process.

Upcoming NIST Standardization Events

As part of their announcement, NIST has allowed the teams behind the submissions to make alterations and improvements to their algorithms by March 15, 2019. These alterations will reflect the current status of the schemes which may have merged, or have changed based on community feedback.

The next round of analysis is expected to last between 12 and 18 months. In that time, each scheme will receive more scrutiny from the cryptographic community. This will be an important time for vulnerable governments and large organizations to carry out proof of concept projects, investigate how the candidates fit into their infrastructure, and address their existing and future needs. Taking these steps now will make it possible to provide invaluable feedback to the standardization effort.

NIST will hold the second Post-Quantum Standardization Conference in Santa Barbara on August 22-24, 2019. By meeting in one central location, cryptographers from around the world can actively exchange ideas and collaborate more effectively. Also, second round candidates are encouraged to present the updates to their schemes at this event.

Why are there multiple rounds in the process?

The standardization process is designed as a series of rounds, with specific candidates eliminated during each round after intense analysis. Simply put, cryptography is extremely difficult, requiring strict attention to details to ensure that nothing is overlooked. Cryptographers from around the world scrutinize each scheme trying to find faults and errors, with the purpose of building confidence and trust in the schemes that make it through each round. The selection process is expected to conclude between 2020-2021, and draft standards for the selection schemes are expected to be available by 2022-2024.

Why were candidates removed from the process?

Many first-round candidates have been eliminated because their security claims did not stand up to scrutiny, or they were significantly less efficient than the average submission. The remaining Round 2 candidates consist of seventeen Public Key Encryption or Key Establishment schemes, which can be used to provide confidentiality. Nine other schemes are Digital Signature schemes, which provide authentication.

Why are there different categories?

All of the schemes can be grouped into families based on their mathematical foundations. Generally speaking, these families are: Lattice-based, Code-based, Multivariate-based, Isogeny-based, (Stateless) Hash-based, or built from symmetric-key primitives and non-interactive zero-knowledge proofs. The majority of the schemes are either Lattice-based or Code-based, with four Multivariate schemes. Each of the remaining categories has one submission each. Each family relies on a different mathematical foundation, but some may offer very different trade-offs with respect to bandwidth requirements, speed, or flexibility.

The distinctions in the underlying math also means that it’s unlikely that more than one category could be significantly weakened by the same kind of attack. Of course, no feasible attacks on any of the second-round candidates are currently known.

Summary of Round Two Selections

Table 1: Public Key Encryption / Key Establishment Candidates
(9) Lattice-based:
Kyber
FrodoKEM
LAC
NewHope
NTRU (merger of NTRUEncrypt and NTRU-HRSS-KEM)
NTRUPrime
Round5 (merger of HILA5 and Round2)
SABER
Three Bears
(7) Code-based:
Classic McEliece
NTS-KEM
BIKE
HQC
LEDAcrypt (merger of LEDAkem and LEDApkc)
Rollo (merger of LAKE, LOCKER, and Ouroboros-R)
RQC
(1) Isogeny-based: 
SIKE
Table 2: Signature Scheme Candidates
(3) Lattice-based:
Dilithium
FALCON
qTesla
(4) Multivariate-based:
GeMSS
LUOV
MQDSS
Rainbow
(1) Stateless Hash-based:
SPHINCS+
(1) Other:
Picnic

ISARA Labs Trends and Insights

Many of the first-round submissions that were based on more exotic, less well-studied assumptions did not make it to the second round due to weaknesses and devastating attacks discovered by the cryptographic community. After all, this is the purpose of the process.

There are technical subtleties which further classify the second-round candidates in each family into more diverse, and more precisely named, sub-categories. The second-round candidates have fairly well-spread coverage across the sub-categories. In particular, the perceived “top” schemes in each sub-category have made it through the first round, whereas any significant outliers in terms of performance or security assessment are gone.

The second-round candidates were selected based on what NIST chose to exclude as opposed to keep. Simply put, candidates were removed based on more obvious deficiencies, rather than subtler details. Given we’re still in the early stages of the standardization process, this is a reasonable strategy.

To summarize, what we’ve seen so far is:

  1. The obviously broken or incomplete schemes have been ruled out.
  2. All the extremely impractical schemes have been ruled out.
  3. Schemes with many similarities have merged.
  4. The outliers in each of the sub-categories have been ruled out.

For Public Key Encryption and Key Establishment schemes, it’s unsurprising that the favoured schemes are the ones that leverage stronger security models.

While some of the second-round candidates do not have formal proofs of security, they may have attractive qualities with respect to smaller bandwidth, faster performance, or are easier to correctly implement. NIST has encouraged the community to further study these candidates to improve our understanding of their security.

Overall, there’s a lot of diversity!

Diversity is the most notable trend among the second-round candidates. It’s likely that candidates from more than one category will be standardized. As before, it’s a good idea to avoid a monoculture where all of our cryptographic schemes are vulnerable to the same kind of attack.

This is because our understanding of the security strengths of cryptographic schemes, and attacks on them, is refined with time.

So, being conservative when selecting candidates for standardization is extremely important. Unfortunately, the quantum-safe candidates whose security has been studied the most are also generally the least efficient.

There are challenges ahead, but with only 26 candidates left to analyze, the next year will likely produce exciting new progress in cryptographic analysis, and along the path to quantum-safe security around the world.