Post-Quantum crypto standardization

Evaluation Criteria

NIST will form an internal selection panel composed of NIST employees to analyze the submitted algorithms; the evaluation process will be discussed in Section 5. All of NIST’s analysis results will be made publicly available.

Although NIST will be performing its own analyses of the submitted algorithms, NIST strongly encourages public evaluation and publication of the results. NIST will take into account its own analysis, as well as the public comments that are received in response to the posting of the “complete and proper” submissions, to make its decisions.

To avoid unnecessary duplication of effort, and to streamline the evaluation process, NIST encourages researchers who are developing similar cryptosystems to combine their efforts and produce a single submission package.

Security

Cost

Algorithm & Implementation Characteristics

4.A      Security

The security provided by a cryptographic scheme is the most important factor in the evaluation. Schemes will be judged on the following factors:

4.A.1 Applications of Public-Key Cryptography NIST intends to standardize post-quantum alternatives to its existing standards for digital signatures (FIPS 186) and key establishment (SP 800-56A, SP 800-56B). These standards are used in a wide variety of Internet protocols, such as TLS, SSH, IKE, IPsec, and DNSSEC. Schemes will be evaluated by the security they provide in these applications, and in additional applications that may be brought up by NIST or the public during the evaluation process. Claimed applications will be evaluated for their practical importance if this evaluation is necessary for deciding which algorithms to standardize.

4.A.2 Security Definition for Encryption/Key-Establishment
NIST intends to standardize one or more schemes that enable “semantically secure” encryption or key encapsulation with respect to adaptive chosen ciphertext attack, for general use. This property is generally denoted IND-CCA2 security in academic literature.

The above security definition should be taken as a statement of what NIST will consider to be a relevant attack. Submitted KEM and encryption schemes will be evaluated based on how well they appear to provide this property, when used as specified by the submitter. Submitters are not required to provide a proof of security, although such proofs will be considered if they are available.

For the purpose of estimating security strengths, it may be assumed that the attacker has access to the decryptions of no more than 2⁶⁴ chosen ciphertexts; however, attacks involving more ciphertexts may also be considered. Additionally, it should be noted that NIST is primarily concerned with attacks that use classical (rather than quantum) queries to the decryption oracle or other private-key functionality. 

4.A.3 Security Definition for Ephemeral-Only Encryption/Key-Establishment   While chosen ciphertext security is necessary for many existing applications (for example, nominally ephemeral key exchange protocols that allow key caching), it is possible to implement a purely ephemeral key exchange protocol in such a way that only passive security is required from the encryption or KEM primitive.

For these applications, NIST will consider standardizing an encryption or KEM scheme which provides semantic security with respect to chosen plaintext attack. This property is generally denoted IND-CPA security in academic literature.

The above security definition should be taken as a statement of what NIST will consider to be a relevant attack. Submitted KEM and encryption schemes will be evaluated based on how well they appear to provide this property, when used as specified by the submitter. Submitters are not required to provide a proof of security, although such proofs will be considered if they are available. Any security vulnerabilities that result from re-using a key should be fully explained.

Back to Top

4.A.4 Security Definition for Digital Signatures NIST intends to standardize one or more schemes that enable existentially unforgeable digital signatures with respect to an adaptive chosen message attack. (This property is generally denoted EUF-CMA security in academic literature.)

The above security definition should be taken as a statement of what NIST will consider to be a relevant attack. Submitted algorithms for digital signatures will be evaluated based on how well they appear to provide this property when used as specified by the submitter. Submitters are not required to provide a proof of security, although such proofs will be considered if they are available.

For the purpose of estimating security strengths, it may be assumed that the attacker has access to signatures for no more than 2⁶⁴ chosen messages; however, attacks involving more messages may also be considered. Additionally, it should be noted that NIST is primarily concerned with attacks that use classical (rather than quantum) queries to the signing oracle. 

4.A.5 Security Strength Categories NIST anticipates that there will be significant uncertainties in estimating the security strengths of these post-quantum cryptosystems. These uncertainties come from two sources: first, the possibility that new quantum algorithms will be discovered, leading to new cryptanalytic attacks; and second, our limited ability to predict the performance characteristics of future quantum computers, such as their cost, speed and memory size.

In order to address these uncertainties, NIST proposes the following approach. Instead of defining the strength of a submitted algorithm using precise estimates of the number of “bits of security,” NIST will define a collection of broad security strength categories. Each category will be defined by a comparatively easy-to-analyze reference primitive, whose security will serve as a floor for a wide variety of metrics that NIST deems potentially relevant to practical security. A given cryptosystem may be instantiated using different parameter sets in order to fit into different categories. The goals of this classification are:

1. To facilitate meaningful performance comparisons between the submitted algorithms, by ensuring, insofar as possible, that the parameter sets being compared provide comparable security.
2. To allow NIST to make prudent future decisions regarding when to transition to longer keys.
3. To help submitters make consistent and sensible choices regarding what symmetric primitives to use in padding mechanisms or other components of their schemes requiring symmetric cryptography.
4. To better understand the security/performance tradeoffs involved in a given design approach.

Back to Top

In accordance with the second and third goals above, NIST will base its classification on the range of security strengths offered by the existing NIST standards in symmetric cryptography, which NIST expects to offer significant resistance to quantum cryptanalysis. In particular, NIST will define a separate category for each of the following security requirements (listed in order of increasing strength²):

1. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g. AES128)
2. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g. SHA256/ SHA3-256)
3. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 192-bit key (e.g. AES192)
4. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 384-bit hash function (e.g. SHA384/ SHA3-384)
5. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 256-bit key (e.g. AES 256)

Here, computational resources may be measured using a variety of different metrics (e.g., number of classical elementary operations, quantum circuit size, etc.). In order for a cryptosystem to satisfy one of the above security requirements, any attack must require computational resources comparable to or greater than the stated threshold, with respect to all metrics that NIST deems to be potentially relevant to practical security.

NIST intends to consider a variety of possible metrics, reflecting different predictions about the future development of quantum and classical computing technology. NIST will also consider input from the cryptographic community regarding this question.

As preliminary guidance to submitters, NIST suggests an approach where quantum attacks are restricted to a fixed running time, or circuit depth. Call this parameter MAXDEPTH. This restriction is motivated by the difficulty of running extremely long serial computations. Plausible values for MAXDEPTH range from 2⁴⁰ logical gates (the approximate number of gates that presently envisioned quantum computing architectures are expected to serially perform in a year³) through 2⁶⁴ logical gates (the approximate number of gates that current classical computing architectures can perform serially in a decade), to no more than 296 logical gates (the approximate number of gates that atomic scale qubits with speed of light propagation times could perform in a millennium).

Back to Top

The complexity of quantum attacks can then be measured in terms of circuit size. These numbers can be compared to the resources required to break AES and SHA3. At the present time, NIST would give the following estimates for the classical and quantum gate counts for the optimal key recovery and collision attacks on AES and SHA3, respectively, where circuit depth is limited to MAXDEPTH^{4, 5}:

AES 128:	2170/MAXDEPTH quantum gates or 2143 classical gates
SHA3-256:	2146 classical gates
AES192:	2233/MAXDEPTH quantum gates or 2207 classical gates
SHA3-384:	2210 classical gates
AES256:	2298/MAXDEPTH quantum gates or 2272 classical gates
SHA3-512:	2274 classical gates

It is worth noting that the security categories based on these reference primitives provide substantially more quantum security than a naïve analysis might suggest. For example, categories 1, 3 and 5 are defined in terms of block ciphers, which can be broken using Grover’s algorithm, with a quadratic quantum speedup. But Grover’s algorithm requires a long-running serial computation, which is difficult to implement in practice. In a realistic attack, one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramati.⁶

Finally, for attacks that use a combination of classical and quantum computation, one may use a cost metric that rates logical quantum gates as being several orders of magnitude more expensive than classical gates. Presently envisioned quantum computing architectures typically indicate that the cost per quantum gate could be billions or trillions of times the cost per classical gate. However, especially when considering algorithms claiming a high security strength (e.g. equivalent to AES256 or SHA384), it is likely prudent to consider the possibility that this disparity will narrow significantly or even be eliminated.

NIST asks submitters to provide a preliminary classification, according to the above categories, for all parameter sets that they intend to be considered for standardization. All submitters are advised to be somewhat conservative in their preliminary classifications, but submitters of algorithms where the complexity of the best known attack has recently decreased significantly, or is otherwise poorly understood, should be especially conservative.

NIST will not require submitters to provide distinct parameter sets for all five security-strength categories. Submitted parameter sets meeting the requirements of a higher category will be automatically considered to meet the requirements of all lower categories. Submitters may also provide more than one parameter set in the same category, in order to demonstrate how parameters can be tuned to offer better performance or higher security margins.

NIST recommends that submitters primarily focus on parameters meeting the requirements for categories 1, 2 and/or 3, since these are likely to provide sufficient security for the foreseeable future. To hedge against future breakthroughs in cryptanalysis or computing technology, NIST also recommends that submitters provide at least one parameter set that provides a substantially higher level of security, above category 3. Submitters can try to meet the requirements of categories 4 or 5, or they can specify some other level of security that demonstrates the ability of their cryptosystem to scale up beyond category 3.

Back to Top

4.A.6 Additional Security Properties While the previously listed security definitions cover many of the attack scenarios that will be used in the evaluation of the submitted algorithms, there are several other properties that would be desirable:

One such property is perfect forward secrecy⁷. While this property can be obtained through the use of standard encryption and signature functionalities, the cost of doing so may be prohibitive in some cases. In particular, public-key encryption schemes with a slow key generation algorithm, such as RSA, are typically considered unsuitable for perfect forward secrecy. This is a case where there is significant interaction between the cost, and the practical security, of an algorithm.

Another case where security and performance interact is resistance to side-channel attacks. Schemes that can be made resistant to side-channel attack at minimal cost are more desirable than those whose performance is severely hampered by any attempt to resist side-channel attacks.  We further note that optimized implementations that address side-channel attacks (e.g., constant-time implementations) are more meaningful than those which do not.

A third desirable property is resistance to multi-key attacks. Ideally an attacker should not gain an advantage by attacking multiple keys at once, whether the attacker’s goal is to compromise a single key pair, or to compromise a large number of keys.

A final desirable, although ill-defined, property is resistance to misuse. Schemes should ideally not fail catastrophically due to isolated coding errors, random number generator malfunctions, nonce reuse, keypair reuse (for ephemeral-only encryption/key establishment) etc.

4.A.7 Other Consideration Factors As public-key cryptography tends to contain subtle mathematical structure, it is very important that the mathematical structure be well understood in order to have confidence in the security of a cryptosystem. To assess this, NIST will consider a variety of factors. All other things being equal, simple schemes tend to be better understood than complex ones. Likewise, schemes whose design principles can be related to an established body of relevant research tend to be better understood than schemes that are completely new, or schemes that were designed by repeatedly patching older schemes that were shown vulnerable to cryptanalysis.

NIST will also consider the clarity of the documentation of the scheme and the quality of the analysis provided by the submitter. Clear and thorough analysis will help to develop the quality and maturity of analysis by the wider community. NIST will also consider any security arguments or proofs provided by the submitter. While security proofs are generally based on unproven assumptions, they can often rule out common classes of attacks or relate the security of a new scheme to an older and better studied computational problem.

In addition to NIST’s own expectations for the scheme’s long-term security, NIST will also consider the judgment and opinions of the broader cryptographic community.

Back to Top

4.B      Cost

As the cost of a public-key cryptosystem can be measured on many different dimensions, NIST will continually seek public input regarding which performance metrics and which applications are most important. If there are important applications that require radically different performance tradeoffs, NIST may need to standardize more than one algorithm to meet these diverse needs.

4.B.1 Public Key, Ciphertext, and Signature Size Schemes will be evaluated based on the sizes of the public keys, ciphertexts, and signatures that they produce. All of these may be important consideration factors for bandwidth-constrained applications or in Internet protocols that have a limited packet size. The importance of public-key size may vary depending on the application; if applications can cache public keys, or otherwise avoid transmitting them frequently, the size of the public key may be of lesser importance. In contrast, applications that seek to obtain perfect forward secrecy by transmitting a new public key at the beginning of every session are likely to benefit greatly from algorithms that use relatively small public keys.

4.B.2 Computational Efficiency of Public and Private Key Operations Schemes will also be evaluated based on the computational efficiency of the public key (encryption, encapsulation, and signature verification) and private key (decryption, decapsulation, and signing) operations. The computational cost of these operations will be evaluated both in hardware and software. The computational cost of both public and private key operations is likely to be important for almost all operations, but some applications may be more sensitive to one or the other. For example, signing or decryption operations may be done by a computationally constrained device like a smartcard; or alternatively, a server dealing with a high volume of traffic may need to spend a significant fraction of its computational resources verifying client signatures.

4.B.3 Computational Efficiency of Key Generation Schemes will also be evaluated based on the computational efficiency of their key generation operations, where applicable. As noted in Section 4.A.6, the most common scenario where key generation time is important is when a public-key encryption algorithm or a KEM is used to provide perfect forward secrecy. Nonetheless, it is possible that key generation times may also be important for digital signature schemes in some applications.

4.B.4 Decryption Failures Some public-key encryption algorithms and KEMs, even when correctly implemented, will occasionally produce ciphertexts that cannot be decrypted/decapsulated. For most applications, it is important that such decryption failures be rare or absent. For algorithms with decryption/decapsulation failures, submitters must provide the failure rate, as well as an analysis of the impact on security that these failures could cause.  While applications can always obtain an acceptably low decryption failure rate by encrypting the same plaintext multiple times, and interactive protocols can simply restart when key establishment fails, these types of solutions have their own performance costs.

Back to Top

4.C      Algorithm and Implementation Characteristics

4.C.1 Flexibility Assuming good overall security and performance, schemes with greater flexibility will meet the needs of more users than less flexible schemes, and therefore, are preferable.

Some examples of “flexibility” may include (but are not limited to) the following:

1. The scheme can be modified to provide additional functionalities that extend beyond the minimum requirements of public-key encryption, KEM, or digital signature (e.g., asynchronous or implicitly authenticated key exchange, etc.).
2. It is straightforward to customize the scheme’s parameters to meet a range of security targets and performance goals.
3. The algorithms can be implemented securely and efficiently on a wide variety of platforms, including constrained environments, such as smart cards.
4. Implementations of the algorithms can be parallelized to achieve higher performance.
5. The scheme can be incorporated into existing protocols and applications, requiring as few changes as possible.

4.C.2 Simplicity The submitted scheme will be judged according to its relative design simplicity.

4.C.3 Adoption Factors that might hinder or promote widespread adoption of an algorithm or implementation will be considered in the evaluation process, including, but not limited to, intellectual property covering an algorithm or implementation and the availability and terms of licenses to interested parties.  NIST will consider assurances made in the statements by the submitter(s) and any patent owner(s), with a strong preference for submissions as to which there are commitments to license, without compensation, under reasonable terms and conditions that are demonstrably free of unfair discrimination.

---

²Note that, barring some truly surprising technological development during the standardization process, NIST will assume that the five security strengths are correctly ordered in terms of practical security. (E.g., NIST will assume that a brute-force collision attack on SHA256 will be technologically feasible before a brute-force key search attack on AES192.)

³See [N. C. Jones, R. Van Meter, A. G. Fowler, P. L. McMahon, J. Kim, T. D. Ladd, and Y. Yamamoto, Layered Architecture for Quantum Computing, Phys. Rev. X 2, 031007 (2012)]  and [M. Mariantoni, Building a Superconducting Quantum Computer, Invited Talk PQCrypto 2014, October 2014 Waterloo, Canada. https://www.youtube.com/watch?v=wWHAs--HA1c (accessed 10/24/2016)]

⁴Quantum circuit sizes are based on the work in [M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt, Applying Grover’s algorithm to AES: quantum resource estimates, in T. Takagi, editor, Post-Quantum Cryptography, Lect. Notes in Comput. Sci. vol. 9606, Springer, pp. 9–43 (2016)].

⁵NIST believes the above estimates are accurate for the majority of values of MAXDEPTH that are relevant to its security analysis, but the above estimates may understate the security of SHA for very small values of MAXDEPTH, and may understate the quantum security of AES for very large values of MAXDEPTH.

⁶See [C. Zalka, Grover’s quantum searching algorithm is optimal, Phys. Rev. A 60, 2746 (1999)]

⁷The term perfect forward secrecy is commonly used to denote a feature of key agreement protocols which gives assurances that past session keys will not be compromised even if the private key of the server is compromised.

Back to Top

---

Call for Proposals