Post-Quantum Cryptography PQC

Algorithm Specifications and Supporting Documentation

Call for Proposals

Each submission must include:

1. a complete written specification
2. a detailed performance analysis
3. Known Answer Test values
4. a thorough description of the expected security strength
5. an analysis of the algorithm with respect to known attacks
6. a statement of advantages and limitations.

Further details are described below.

2.B.1  
A complete written specification of the algorithms shall be included, consisting of all necessary mathematical operations, equations, tables, and diagrams that are needed to implement the algorithms. The document shall also include a design rationale, and an explanation for all the important design decisions that have been made. 

Each submission package shall describe a collection of algorithms, also called a cryptosystem or cryptographic scheme, that implements one or more of the following functionalities: public-key encryption, key encapsulation mechanism¹ (KEM), and digital signature. Public-key encryption schemes shall include algorithms for key generation, encryption, and decryption. KEM schemes shall include algorithms for key generation, encapsulation, and decapsulation. Digital-signature schemes shall include algorithms for key generation, signature generation and signature verification.

If a submission includes more than one type of scheme, NIST will evaluate the schemes of each type separately.  Submitters may choose to combine different types of schemes into a single submission.  They may also instead prepare and submit a complete submission package for each algorithm, making sure to include all supporting documents and intellectual property statements in each individual package.

As the KEM and public-key encryption functionalities can generally be interconverted, unless the submitter specifies otherwise, NIST will apply standard conversion techniques to convert between schemes if necessary.

For algorithms that have tunable parameters (such as the dimension of some underlying vector space, or the number of equations and variables), the submission document shall specify concrete values for these parameters. If possible, the submission should specify several parameter sets that allow the selection of a range of possible security/performance tradeoffs. In addition, the submitter should provide an analysis of how the security and performance of the algorithms depend on these parameters. To facilitate the analysis of these algorithms by the cryptographic community, submitters are encouraged to also specify parameter sets that provide lower security levels, and to provide concrete examples that demonstrate how certain parameter settings affect the feasibility of known cryptanalytic attacks.

Specific parameter sets may permit NIST to select a different performance/security tradeoff than originally specified by the submitter, in light of discovered attacks or other analysis, and in light of the alternative algorithms that are available. NIST will consult with the submitter of the algorithm, as well as the cryptographic community, if it plans to select that algorithm for development as a NIST standard, but with a different parameter set than originally specified by the submitter.

A complete submission shall specify any padding mechanisms and any uses of NIST-approved cryptographic primitives that are needed in order to achieve security. If the scheme uses a cryptographic primitive that has not been approved by NIST, the submitter shall provide an explanation for why a NIST-approved primitive would not be suitable.

To help rule out the existence of possible back-doors in an algorithm, the submitter shall explain the provenance of any constants or tables used in the algorithm.

2.B.2 The submitter must also include a statement regarding the algorithm’s estimated computational efficiency and memory requirements for the “NIST PQC Reference Platform” (specified in Section 5.B). Efficiency estimates for other platforms may be included at the submitter’s discretion. These estimates shall each include the following information, at a minimum:

1. A description of the platform used to generate the estimate, in sufficient detail so that the estimates could be verified in the public evaluation process.  For software implementations, include information about the processor, clock speed, memory, and operating system, on which the performance estimates were obtained. For hardware estimates, a gate count (or estimated gate count) should be included.
2. A speed estimate and memory requirements for the algorithm(s) on the reference platform specified in Section 5.B. At a minimum, the number of milliseconds or clock cycles required to perform each required operation (e.g., key generation, encryption, decryption, sign, verify), and the size of all inputs and outputs (e.g., keys, ciphertexts, signatures).

2.B.3 In addition, each submission package is required to include Known Answer Test (KAT) values that can be used to determine the correctness of an implementation of the submitted algorithms. The KATs are individual input tuples that produce single output values, e.g., an input tuple of a key and plaintext resulting in an output of the corresponding ciphertext. If an algorithm uses random values, the KAT should specify a fixed value for the random bits used by the algorithm, in order to force the algorithm to produce a fixed output value. Separate KATs should be provided to test different aspects of the algorithm, e.g., key generation, encryption, decryption, sign, verify, etc.

The KATs shall be included as specified below. All of these KAT values shall be submitted electronically, in separate files, on a CD–ROM, DVD, USB flash drive, or included in a zip file as described in Section 2.C.

Each file must be clearly labeled with header information listing:

1. Algorithm name,
2. Test name,
3. Description of the test, and
4. Other parameters.

The list must be followed by a set of tuples where all values within the tuple are clearly labeled (e.g., Plaintext, PublicKey, RandomBits, Ciphertext, etc.). Sample files for these KAT values will be posted at http://www.nist.gov/pqcrypto.

All applicable KATs that can be used to verify various features of the algorithm shall be included. A set of KATs shall be included for each security strength specified in Section 4.A. Required KATs include:

1. If the execution of an algorithm produces intermediate results that are informative (e.g., for debugging an implementation of the algorithm), then the submitter shall include known answers for those intermediate values for each of the required security strengths. Examples of providing such intermediate values are available at: http://csrc.nist.gov/groups/ST/toolkit/index.html.
2. If tables are used in an algorithm, then a set of KAT vectors shall be included to make use of the table entries.

Note: The submitter is encouraged to include any other KATs that test different features of the algorithm (e.g., for permutation tables, padding scheme, etc.). The purposes of these tests shall be clearly described in the file containing the test values.

2.B.4 The submission package shall include a statement of the expected security strength of the cryptosystem, along with a supporting rationale. For each parameter set the submitter wishes NIST to consider for standardization, the submitter shall specify a security definition from sections 4.A.2, 4.A.3, or 4.A.4, as well as an estimated security strength according to the categories given in section 4.A.5. All submitters are advised to be somewhat conservative in assigning parameters to a given category, 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. Submitters should give quantitative estimates for any additional security provided by their settings above and beyond the minimum security strength provided by the relevant security strength category. Such estimates should include, at a minimum, a claimed classical security strength. Furthermore, the statement should address the additional attack scenarios identified in Section 4.A.6.

2.B.5 The submission package shall include a statement that summarizes the known cryptanalytic attacks on the scheme, and provides estimates of the complexity of these attacks.

The submitter shall provide a list of references to any published materials describing or analyzing the security of the submitted algorithm or cryptosystem. When possible, the submission of copies of these materials (accompanied by a waiver of copyright or permission from the copyright holder for public evaluation purposes) is encouraged.

2.B.6 The submission package shall include a statement that lists and describes the advantages and limitations of the cryptosystem. Such advantages and limitations may involve the assessment of the cryptosystem’s security against classical and quantum attacks, as well as any unusual characteristics of the scheme, such as extra functionalities, performance tradeoffs, and unusual vulnerabilities. This statement may also discuss the ease of implementing and deploying the algorithms, and their compatibility with existing protocols, networks and applications.  This could include, for example, the suitability of the algorithm for use in hybrid schemes, which may be part of the transition to post-quantum cryptosystems.

In addition, this statement may address the ability to implement the algorithms in various environments, including, but not limited to 8-bit processors (e.g., smartcards), voice applications, satellite applications, or other environments where low power, constrained memory, or limited real-estate are consideration factors. To demonstrate the efficiency of a hardware implementation of the algorithm, the submitter may include a specification of the algorithm in a nonproprietary hardware description language (HDL).