Post-Quantum Cryptography PQC

Cost (Evaluation Criteria)

Call for Proposals

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.