Summary Evaluation of NIST Post-Quantum Cryptography Candidates Performed by the Center for Cybersecurity

Introduction

The Canadian Center for Cyber ​​Security (Cyber ​​Center), part of the Communications Security Establishment, is Canada's cyber security authority. The Center for Cyber ​​Security is a partner of the National Institute of Standards and Technology (NIST) in the Cryptographic Module Validation Program (CMPV) . It recommends the use of NIST cryptographic standards mentioned in its guidance documents, such as ITSP.40.111. Cryptography scientists at the Center for Cybersecurity conduct finalist and other Post-Quantum Cryptography (PQC) candidates' evaluations to support the selection process and ensure that Candidates selected for standardization continue to provide cryptographic protection to information and systems that will be important to Canada and Canadians after the arrival of quantum computers. The views expressed herein are strictly those of the Center for Cyber ​​Security.

context

In 1994, Peter Shor invented an algorithm that could efficiently solve the mathematical problems underlying modern asymmetric cryptography when run on a large quantum computer. Although these large quantum computers are still non-existent, several researchers believe that they could become reality within the next decades. This finding is the reason for the considerable research effort devoted to post-quantum PQC cryptography, a field aimed at ensuring the security of encryption after the arrival of large quantum computers.

With this in mind, the US National Institute of Standards and Technology NIST launched a new PQC initiative in 2016 with the goal of standardizing one or more post-quantum cryptographic algorithms ( NIST's PQC Standards Process , in English only). The 2 types of algorithms considered are: public key encryption models (used to encrypt messages or establish shared secret keys) and signature models (used to digitally sign messages).

November 2017 was the deadline for sending initial submissions to the standards process and a month later, in December, NIST announced that it had received 69 valid submissions. These came from researchers in more than 25 countries and used techniques from several different mathematical families, including Euclidean networks, error-correcting codes, multivariate equations, hash functions, and elliptic curves. . This kicked off the first round of judging. In January 2019, the second round had only 26 candidates left and the third round officially began in July 2020.

The third round has two types of candidates: 7 finalists and 8 substitutes. NIST expects one or more finalists to be chosen and standardized at the end of Round Three. The surrogates have been selected for further review in anticipation that some of these algorithms may be standardized after a fourth round of evaluation.

Although security is still the most important criteria, the speed and bandwidth requirements of the algorithm remain critical factors in the standardization process. At the start of the third round, NIST indicated that cryptography based on Euclidean lattices was the most promising family for general use. Five of the seven finalists were based on Euclidean lattices, and NIST would like to standardize (at most) one encryption algorithm based on Euclidean lattices and (at most) one signature algorithm based on Euclidean lattices at the end of the third round. The other 2 finalists, the first being based on coding theory and the second being based on multivariate polynomials, are not suitable for general use since they require a lot of bandwidth. These other finalists (and their substitutes), however, offer advantages of their own. The next section will offer a brief description of the mathematical family to which the finalist and substitute candidates belong, and will discuss their advantages and disadvantages.

Math families

Euclidean networks

The security of cryptography based on Euclidean networks is based on mathematical problems related to them. This is an active area of ​​research, a fact often attributed to the famous "worst-to-medium" case complexity analysis developed by Ajtai in 1996. Twenty-six of the initial 69 submissions were network-based, as was 5 of the 7 finalists. At first glance, many of the techniques employed in submissions submitted through the process may not look like network issues, but their best-known security evidence and attacks are based on the complexity of network issues. The five finalists use variants of the NTRU problem or the Learning with Errors (LWE) problem,

The NTRU problem was introduced over 20 years ago and is based on factoring a certain polynomial function into a product consisting of 2 polynomials with special properties. The best known attacks against the NTRU problem are based on networks and 2 finalists in the third round use the NTRU problem.

Like the theory-based cryptography described in the next section, the LWE problem is a modification of a simple linear algebra problem whose solution has been made more complex by intentionally adding errors to it. The initial LWE problem requires very large public keys and is slower than the network-based finalists that NIST considered. LWE-based finalists use changes to the LWE to allow for the creation of smaller keys and speed up processing.

Among the remaining candidates, network-based approaches are the only ones to offer encryption and signing functions, and the fastest in both categories. Although specialized proposals may provide better performance, network-based approaches provide advantageous performance with respect to bandwidth requirements, making them excellent candidates for general use.

Error correction codes

Code-based cryptography is based on the theory of error-correcting codes. Error correction codes are traditionally used in information theory to solve problems unrelated to cryptography: two parties want to communicate through a noisy channel, which means that the messages sent contain errors when they reach their destination. Error correction codes are used to remove the error and recover the original message. In most code-based cryptographic solutions, the concept of key corresponds to errors that are intentionally inserted in such a way that they can only be identified or removed by the holder of the secret key. Without the latter,

Code-based cryptography was first proposed over 40 years ago in the form of McEliece's cipher model. Seventeen code-based encryption models and 2 code-based signatures had been submitted as part of NIST's initial request for PQC applicants. Of these, 3 cipher models were still among the candidates for the third round: 1 finalist and 2 substitutes. The finalist is a McEliece model that uses Goppa codes, while the surrogate models use families of codes different from those used by the traditional McEliece model: the first uses moderate density parity check codes (MDPC for Moderate Density Parity Check) quasi-cyclic and the second, random quasi-cyclic codes.

Unfortunately, the public keys of the original McEliece model are extremely large, a problem which remains one of the main drawbacks of code-based encryption systems today. Variants of the underlying code family have often been proposed to correct the situation, but in best-case scenarios the public keys of code-based systems are larger than those employed by finalist Euclidean lattice-based systems. The main advantages of McEliece's system are the level of security afforded by its maturity, the very small ciphertexts (smaller than other models) it employs, and the speed at which it is able to perform encapsulation. and decapsulation (very fast).

Systems of Multivariate Quadratic Equations

Multivariate Quadratic Models (MVQ) are based on solving second degree polynomial systems having 2 or more variables in a finite field. A typical MVQ pattern builds a system in such a way that only the holder of the secret key can find the solution. To do this, one must construct the equations from a special structure and hide them in such a way as to appear random to an attacker. In the first round of the NIST standards process, 7 MVQ signature patterns and 2 MVQ encryption patterns were submitted. In the third round, there were 2 MVQ signings: a finalist and a substitute.

One advantage of MVQ signature patterns is that they generate very small signatures (in some cases, smaller than the RSA signatures in use today). In the case of the finalist, these small signatures speed up the signing process. Progress was made on recent security theory research on MVQ models, which resulted in parameter level changes for the Round 3 finalist and raised questions about the stability of the MVQ models. complex MVQ problems. The size of the public (and sometimes private) keys of MVQ signature templates is one of the drawbacks of this approach, which makes it unsuitable for general use.

Hash functions

Hash-Based Signature (HBS) signatures rely solely on the security of a cryptographic hash function, which is an irreversible function that uses a string of any length to generate a fixed-length output. Larger output sizes are believed to be safe from quantum computers. According to this concept, an HBS is a collection of several unique signature models (OTS for One-Time Signature), which means that each OTS can sign only one message. It uses a data structure called a tree to efficiently combine the many OTSs. An HBS chooses a single OTS from its collection and uses it to sign the message. The major issue is that the HBS must never select the same OTS more than once, otherwise security will be compromised. The most efficient HBS models are stateful, which means that the HBS needs to know which OTSs have already been used. This process requires a state management procedure which might not be possible in some applications. NIST has published its recommendations on stateful hash-based signatures.

Two stateless HBS models were submitted in NIST's initial PQC application, including one that is still being considered as a third-round surrogate model. The idea is to use a very large tree structure and to choose the OTS randomly. If the tree structure is wide enough, there is very little risk that an OTS will be reused. Although several improvements have been made to stateless HBS models, signatures are large and performance is slow compared to other PQC signature candidates. Nevertheless, hash-based signatures offer a high degree of confidence in their security, which is why they are still under consideration.

Isogenies of elliptic curves

Isogeny-based cryptography uses transformations between elliptic curves to build public-key cryptosystems. The elliptic curves employed by public-key cryptosystems are known to be vulnerable to quantum computers. That said, since isogeny-based models do not use the same arithmetic operations, it is believed that they will be able to withstand post-quantum cryptography mechanisms. The only isogeny-based submission received in the NIST standards process is the Cipher Model which is still under consideration in Round 3 as an alternate candidate. Interest in public keys remains, because they are smaller than those of the other contenders and the size of the ciphertexts is also very small. Although this model has undergone several optimizations, it is much slower than its competitors. As with the other surrogate candidates, NIST has suggested that isogeny-based cryptography could benefit from further research to be conducted in Round 3.

Others

Some of the original 69 submissions did not fall into any of the previous categories. Among these submissions are rank-metric codes (a variant of coding theory), random walks, and braids. Only the signature model that incorporates symmetric cryptography and what is called a “zero-knowledge proof” remains a substitute model for the third round. This model uses a small public key size, but it takes longer to sign and the signatures are larger. As with hash-based candidates, this model offers security that relies exclusively on symmetric cryptography, which is one of its main advantages. Being based on a relatively new concept, it has not been the subject of an in-depth study compared to models belonging to other families. For this reason, significant improvements were noted during the first two rounds and NIST believes that this trend could be repeated in subsequent rounds. This novelty has the downside, however, that it will take longer before the crypto community has confidence in the level of security it provides.

Conclusion

It is expected that the third round of evaluation of PQC candidates will last 12-18 months, and that NIST will select a small number of candidates from the finalists to proceed with standardization by early 2022 and to come to a final standard by 2024. NIST also plans to conduct a fourth round of evaluation for surrogate applicants or finalists who require further evaluation, which may result in further standards to be a later date. While Euclidean lattices seem to be best suited for general use, the cryptographic community will continue to examine the other families for the advantages they provide for particular use cases and the diversity they offer should attacks against Euclidean networks become more sophisticated. Given the limited number of candidates still in contention for Round 3, NIST expects the cryptography research community to be able to conduct a more thorough review of each candidate in areas such as side-channels, performance data in Internet protocols, and performance data in hardware deployment, as well as rigorous and ongoing security analysis.

For more details on NIST's PQC standardization, please visit NIST's official Post-Quantum Cryptography website or see NIST's Round 2 Progress Report ( NISTIR 8309in English only), 2 sources that were widely consulted during the writing of this blog. The Cyber ​​Center strongly recommends that consumers await the completion of standards related to post-quantum encryption and public-key signing models before using PQC candidates to protect their data or systems. For now, what matters is to plan a cryptographic migration by listing the systems that need to be protected by post-quantum mechanisms and preparing them accordingly.