NIST Standardization

Posted on April 18, 2018

First NIST standardization conference - April 11-13, 2018

— Thomas Attema

Last week the first NIST PQC standardization conference took place in Fort Lauderdale, Florida. This was the first meeting of a multi-year process to standardize a variety of quantum-resistant cryptographic protocols. The conference was co-located with the PQCrypto 2018 conference and attracted a lot of interest, from both academia and industry, with well over 300 attendees.

From all over the world a total of 82 protocols were submitted by the end of 2017, 69 of these protocols were accepted as they followed the guidelines provided by NIST. These submissions have induced a significant effort into the analysis of these schemes. New insights have led to 5 submissions being withdrawn from the standardization process. Almost all of the remaining 64 proposals were presented during this conference.

Signatures KEM / Encryption Overall
Lattice-based 5 21 26
Code-based 2 17 19
Multi-variate 7 2 9
Symmetric / hash-based 3 3
Other 2 5 7
Total 19 45 64

NIST emphasized that this standardization process will be much more complex than the previous AES and SHA-3 standardization processes. Not only public-key encryption schemes and key encapsulation mechanisms, but also signature schemes will be considered. Moreover, the fundamental building blocks upon which the various protocols are based vary greatly, resulting in substantially different advantages and disadvantages amongst the submissions. For these reasons, this process will most likely not result in the standardization of a single protocol, but rather the standardization of multiple protocols.

Dan Bernstein got to kick-off the conference with a presentation on the post-quantum RSA submission. Despite being a somewhat humorous proposal leading to prohibitively large key-sizes, the presentation had a serious note. It was argued that familiarity should be an important criterion in selecting a protocol to standardize. The fact that RSA is still extensively used demonstrates that people like to apply protocols they are familiar with. Familiar schemes should therefore be included in the standards to stimulate adaptation and the transition to quantum-resistant infrastructures.

During this conference it became clear that the path to a number of standardized quantum-resistant protocols is not set in stone, and many unknowns remain. NIST is open to suggestions and will keep consulting the cryptographic community. During the discussions Adi Shamir made a proposal to work towards three categories of promising protocols: production, development and research protocols. These categories range from well-studied protocols ready to be deployed, to new and innovative ones based on assumptions and reductions that are still to be studied.

One of the unknowns in this process is how the number of submissions will be reduced. NIST aims to select a subset of the submissions early in 2019 to continue in the second round. Since there is quite some overlap between various submissions, NIST is aiming for various teams to merge and to continue the process collaborating on a single submission. At this point NIST is hesitant to force teams to merge and hopes these mergers will be initiated by the submitters.

Another interesting, but unconcluded, discussion targeted the security models that should be used in the evaluation of the various submissions. In particular, Steven Galbraith emphasized that there are different (quantum) security models available and we should agree on the one to use. Similarly the issue of patented submissions was raised. Some had a more pronounced opinion on this matter than others, but NIST decided not to exclude patented submissions at this stage of the standardization process.

The standardization process thus contains a wide variety of submissions, ranging from very conservative to more exotic. NIST is very happy to see the effort that is put into analyzing all the submissions and aims to use the feedback from the cryptographic community to select a number of submissions to continue to round 2. The remaining teams will have the opportunity to make minor adjustments to their submissions and present their results at the second standardization meeting that will be organized in August 2019, co-located with Crypto 2019.