In some of our previous posts, we have already touched upon why the development of quantum computers poses challenges to the field of information security and how the standardisation bodies, most notably NIST, prepare for the post-quantum era of computing. This process reached its next milestone yesterday when NIST has announced which key-establishment mechanism and digital signature schemes will be standardized soon.
What has happened so far?
The National Institute of Standards and Technology (NIST) initiated the standardization of post-quantum secure public-key encryption (or key encapsulation) and digital signatures back in 2016. In the past six years, the standardization process had three rounds. At the end of each, the best candidates were selected, thus reducing the number of competing digital signature schemes from the submitted initially 22, first to 9 and then to 6. During the different rounds, anyone could propose attacks and fixes, providing public scrutiny for the candidates. In July 2020, third round candidates were announced in two categories: in case of signatures, three finalists and three “alternate candidates” were selected in line with the goal of choosing more schemes to provide diversity. This goal was essential because of two reasons. First, the different candidates turned out to have various benefits, e.g. signature sizes can be rather different, which can be crucial in some applications and less critical in others. Another reason to prefer diversity in the standardization is related to the effort to avoid future exposure to possible weaknesses of a single concept or technology. At this point, it is worth remembering why we have to standardize new techniques. The main reason is that a new technology (namely the quantum computer) threatens our currently used and standardized public-key methods because they all share some common properties (see our previous post on this).
The dawn of a new era
According to yesterday’s announcement, NIST will create new draft standards for CRYSTALS-KYBER (for key establishment) and CRYSTALS-Dilithium (a digital signature) authored by the “CRYSTALS Team” that consists of renowned researchers from various research institutes. Their witty name both refers to the underlying structure that their solutions are using and abbreviates “CRYptographic SuiTe for Algebraic LatticeS”. To fulfil the above mentioned goals, two other digital signature schemes will also be standardized: FALCON (i.e. Fast-Fourier Lattice-based Compact Signatures over NTRU) because of its short signatures (besides other favourable properties) and SPHINCS+ that is a hash-based signature scheme, not relying on lattices (a word that is disquietingly present in the names of all the other schemes to standardize).
What to expect next?
Of course, this is not the end of the story. First of all, the draft standards have to be prepared with a lot of care that may last until 2024, according to the official timeline. Moreover, a 4th round has just started for key establishment to select alternate candidates. Instead of another round, for signatures NIST plans to issue a new call for proposals for public-key (quantum-resistant) algorithms by the end of this summer, with the expected submission deadline of June 1, 2023. The main reasons behind this new call are the already mentioned motivation for diversification; the goal of standardizing techniques that lead to short signatures and fast verification; and also the rapid development of the field. Since the original call six years ago, several promising techniques started their rapid development (e.g. under the umbrella of the so-called isogeny-based cryptography), so we can expect many new exciting candidates by next summer.