Sol Cates | Principal Technologist, Data Protection
The National Institute of Standards and Technology (NIST)’s Post-Quantum Cryptography Standardization project second round candidates have just been announced, a thinned-down selection of the 71 entries submitted by November 2017. In the past year, NIST has been assessing the submissions, and scrutinizing them for security and efficiency. The goal of the project is to create a set of standards for protecting electronic information from attack by the computers of today and in the future.
The competition has seen great engagement from the cryptographic community, with the large number of entries and lively analysis/debate being promising signs that highly-secure, studied, trusted and efficient algorithms will emerge in 2022-2024.
The second-round candidates comprise a varied and diverse selection of the original submissions, covering all of the main algorithm families, but with a few surprises.
Quantum-resistant algorithms rely on one of four main types of difficult problems, against which quantum computers are thought to offer no benefit: lattices; hashes; codes; or multivariate quadratic polynomial problems.
The selected algorithms fall into two categories: those which allow public-key encryption (17 selected) and key establishment, and those for creating digital signatures (9 selected).
In the public-key encryption and key establishment selections, 53% of the second-round candidates are based on lattice problems. These lattice problems have unique theoretical security properties, leading to them being the most popular of the quantum-resistant public-key schemes, hence it’s not a surprise they occupy the lion’s share of the selections. In second place are code-based schemes with 41%.
A surprise inclusion is the Classical McEliece scheme, a code-based scheme that dates back to 1978 but has rarely seen use due to large key sizes. It would be ironic if the McEliece scheme were to finally come into use, 45 years after its invention. If McEliece had become the standard public key algorithm in place of (quantum-vulnerable) RSA in the late 1970s, quantum computing would not be such a threat to modern cryptography.
The final scheme in the public-key category is a supersingular isogeny scheme, a relatively new category but one that’s seen experimentation by Microsoft and Cloudflare. This is one to watch.
In the signature category, only three of the nine are lattice-based, while almost half are Multivariate Quadratic (MQ) based. MQ schemes, while attractive in terms of efficiency, have a long and chequered history of catastrophic mathematical vulnerabilities, with no MQ-based scheme ever seeing meaningful real-world use – the inclusion of so many MQ schemes is a surprise. Another surprise comes in the inclusion of only a single hash-based scheme – but maybe this is a sign that hash-based schemes have reached an optimal state, with only a single scheme being required.
A significant number of the round two candidates are encumbered by patents: 47% of the public-key entries and 22% of the signature entries. So far, this doesn’t seem to have affected NIST’s choices, with a similar proportion of round one entries falling under patents.
NIST will hold a standardization conference in August, followed by the beginning of a third round as early as next year, if enough viable candidates remain.
We at Thales will continue to closely follow the progress of the standardization effort but think that the NIST effort is yielding great results so far, particularly in bringing together the worldwide cryptographic community to ensure that we're ready for the arrival of large-scale quantum computing. Our in-house research team has been experimenting with several of the candidate algorithms since 2017 to prepare our products and services for the coming quantum computing revolution, and will continue to do so as the effort progresses and the best algorithms are selected.
For more information on the candidates that will be moving on to the second round of the NIST PQC Standardization Process, click here.
To learn more about the innovative projects and thought leadership from our worldwide research teams at Thales eSecurity, visit our Horizons research portal for more information.