Post-Quantum Cryptography Standardization [1] is a program and competition by NIST to update their standards to include post-quantum cryptography. [2] It was announced at PQCrypto 2016. [3] 23 signature schemes and 59 encryption/KEM schemes were submitted by the initial submission deadline at the end of 2017 [4] of which 69 total were deemed complete and proper and participated in the first round. Seven of these, of which 3 are signature schemes, have advanced to the third round, which was announced on July 22, 2020.
On August 13, 2024, NIST released final versions of the first three Post Quantum Crypto Standards. [5]
Academic research on the potential impact of quantum computing dates back to at least 2001. [6] A NIST published report from April 2016 cites experts that acknowledge the possibility of quantum technology to render the commonly used RSA algorithm insecure by 2030. [7] As a result, a need to standardize quantum-secure cryptographic primitives was pursued. Since most symmetric primitives are relatively easy to modify in a way that makes them quantum resistant, efforts have focused on public-key cryptography, namely digital signatures and key encapsulation mechanisms. In December 2016 NIST initiated a standardization process by announcing a call for proposals. [8]
The competition is now in its third round out of expected four, where in each round some algorithms are discarded and others are studied more closely. NIST hopes to publish the standardization documents by 2024, but may speed up the process if major breakthroughs in quantum computing are made.
It is currently undecided whether the future standards will be published as FIPS or as NIST Special Publication (SP).
Under consideration were: [9]
(strikethrough means it had been withdrawn)
Type | PKE/KEM | Signature | Signature & PKE/KEM |
---|---|---|---|
Lattice |
|
| |
Code-based |
| ||
Hash-based |
| ||
Multivariate |
|
|
|
Braid group |
| ||
Supersingular elliptic curve isogeny | |||
Satirical submission | |||
Other |
|
|
Candidates moving on to the second round were announced on January 30, 2019. They are: [33]
Type | PKE/KEM | Signature |
---|---|---|
Lattice | ||
Code-based | ||
Hash-based |
| |
Multivariate | ||
Supersingular elliptic curve isogeny | ||
Zero-knowledge proofs |
|
On July 22, 2020, NIST announced seven finalists ("first track"), as well as eight alternate algorithms ("second track"). The first track contains the algorithms which appear to have the most promise, and will be considered for standardization at the end of the third round. Algorithms in the second track could still become part of the standard, after the third round ends. [53] NIST expects some of the alternate candidates to be considered in a fourth round. NIST also suggests it may re-open the signature category for new schemes proposals in the future. [54]
On June 7–9, 2021, NIST conducted the third PQC standardization conference, virtually. [55] The conference included candidates' updates and discussions on implementations, on performances, and on security issues of the candidates. A small amount of focus was spent on intellectual property concerns.
Type | PKE/KEM | Signature |
---|---|---|
Lattice | ||
Code-based |
| |
Multivariate |
Type | PKE/KEM | Signature |
---|---|---|
Lattice |
| |
Code-based | ||
Hash-based |
| |
Multivariate |
| |
Supersingular elliptic curve isogeny | ||
Zero-knowledge proofs |
|
After NIST's announcement regarding the finalists and the alternate candidates, various intellectual property concerns were voiced, notably surrounding lattice-based schemes such as Kyber and NewHope. NIST holds signed statements from submitting groups clearing any legal claims, but there is still a concern that third parties could raise claims. NIST claims that they will take such considerations into account while picking the winning algorithms. [56]
During this round, some candidates have shown to be vulnerable to some attack vectors. It forces these candidates to adapt accordingly:
On July 5, 2022, NIST announced the first group of winners from its six-year competition. [60] [61]
Type | PKE/KEM | Signature |
---|---|---|
Lattice | ||
Hash-based |
On July 5, 2022, NIST announced four candidates for PQC Standardization Round 4. [62]
Type | PKE/KEM |
---|---|
Code-based | |
Supersingular elliptic curve isogeny |
On August 13, 2024, NIST released final versions of its first three Post Quantum Crypto Standards. [5] According to the release announcement:
While there have been no substantive changes made to the standards since the draft versions, NIST has changed the algorithms’ names to specify the versions that appear in the three finalized standards, which are:
- Federal Information Processing Standard (FIPS) 203, intended as the primary standard for general encryption. Among its advantages are comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation. The standard is based on the CRYSTALS-Kyber algorithm, which has been renamed ML-KEM, short for Module-Lattice-Based Key-Encapsulation Mechanism.
- FIPS 204, intended as the primary standard for protecting digital signatures. The standard uses the CRYSTALS-Dilithium algorithm, which has been renamed ML-DSA, short for Module-Lattice-Based Digital Signature Algorithm.
- FIPS 205, also designed for digital signatures. The standard employs the Sphincs+ algorithm, which has been renamed SLH-DSA, short for Stateless Hash-Based Digital Signature Algorithm. The standard is based on a different math approach than ML-DSA, and it is intended as a backup method in case ML-DSA proves vulnerable.
- Similarly, when the draft FIPS 206 standard built around FALCON is released, the algorithm will be dubbed FN-DSA, short for FFT (fast-Fourier transform) over NTRU-Lattice-Based Digital Signature Algorithm.
NIST received 50 submissions and deemed 40 to be complete and proper according to the submission requirements. [65] Under consideration are: [66]
(strikethrough means it has been withdrawn)
Type | Signature |
---|---|
Lattice | |
Code-based | |
MPC-in-the-Head | |
Multivariate |
|
Supersingular elliptic curve isogeny |
|
Symmetric-based | |
Other |
|
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys to provide equivalent security, compared to cryptosystems based on modular exponentiation in Galois fields, such as the RSA cryptosystem and ElGamal cryptosystem.
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.
The Advanced Encryption Standard (AES), the symmetric block cipher ratified as a standard by National Institute of Standards and Technology of the United States (NIST), was chosen using a process lasting from 1997 to 2000 that was markedly more open and transparent than its predecessor, the Data Encryption Standard (DES). This process won praise from the open cryptographic community, and helped to increase confidence in the security of the winning algorithm from those who were suspicious of backdoors in the predecessor, DES.
Daniel Julius Bernstein is an American mathematician, cryptologist, and computer scientist. He is a visiting professor at CASA at Ruhr University Bochum, as well as a research professor of Computer Science at the University of Illinois at Chicago. Before this, he was a visiting professor in the department of mathematics and computer science at the Eindhoven University of Technology.
NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unlike other popular public-key cryptosystems, it is resistant to attacks using Shor's algorithm. NTRUEncrypt was patented, but it was placed in the public domain in 2017. NTRUSign is patented, but it can be used by software under the GPL.
In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling.
The vast majority of the National Security Agency's work on encryption is classified, but from time to time NSA participates in standards processes or otherwise publishes information about its cryptographic algorithms. The NSA has categorized encryption items into four product types, and algorithms into two suites. The following is a brief and incomplete summary of public knowledge about NSA algorithms and protocols.
Paulo Licciardi Barreto is a Brazilian-American cryptographer and one of the designers of the Whirlpool hash function and the block ciphers Anubis and KHAZAD, together with Vincent Rijmen. He has also co-authored a number of research works on elliptic curve cryptography and pairing-based cryptography, including the eta pairing technique, identity-based cryptographic protocols, and the family of Barreto–Naehrig (BN) and Barreto–Lynn-Scott (BLS) pairing-friendly elliptic curves. More recently he has been focusing his research on post-quantum cryptography, being one of the discoverers of quasi-dyadic codes and quasi-cyclic moderate-density parity-check (QC-MDPC) codes to instantiate the McEliece and Niederreiter cryptosystems and related schemes.
NTRUSign, also known as the NTRU Signature Algorithm, is an NTRU public-key cryptography digital signature algorithm based on the GGH signature scheme. The original version of NTRUSign was Polynomial Authentication and Signature Scheme (PASS), and was published at CrypTEC'99. The improved version of PASS was named as NTRUSign, and was presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003. The 2003 publication included parameter recommendations for 80-bit security. A subsequent 2005 publication revised the parameter recommendations for 80-bit security, presented parameters that gave claimed security levels of 112, 128, 160, 192 and 256 bits, and described an algorithm to derive parameter sets at any desired security level. NTRU Cryptosystems, Inc. have applied for a patent on the algorithm.
Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field . In certain cases those polynomials could be defined over both a ground and an extension field. If the polynomials have the degree two, we talk about multivariate quadratics. Solving systems of multivariate polynomial equations is proven to be NP-complete. That's why those schemes are often considered to be good candidates for post-quantum cryptography. Multivariate cryptography has been very productive in terms of design and cryptanalysis. Overall, the situation is now more stable and the strongest schemes have withstood the test of time. It is commonly admitted that Multivariate cryptography turned out to be more successful as an approach to build signature schemes primarily because multivariate schemes provide the shortest signature among post-quantum algorithms.
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.
The NIST hash function competition was an open competition held by the US National Institute of Standards and Technology (NIST) to develop a new hash function called SHA-3 to complement the older SHA-1 and SHA-2. The competition was formally announced in the Federal Register on November 2, 2007. "NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES)." The competition ended on October 2, 2012, when NIST announced that Keccak would be the new SHA-3 hash algorithm.
SHA-3 is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015. Although part of the same series of standards, SHA-3 is internally different from the MD5-like structure of SHA-1 and SHA-2.
Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. Most widely-used public-key algorithms rely on the difficulty of one of three mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm or even faster and less demanding alternatives.
BLISS is a digital signature scheme proposed by Léo Ducas, Alain Durmus, Tancrède Lepoint and Vadim Lyubashevsky in their 2013 paper "Lattice Signature and Bimodal Gaussians".
Hash-based cryptography is the generic term for constructions of cryptographic primitives based on the security of hash functions. It is of interest as a type of post-quantum cryptography.
In post-quantum cryptography, NewHope is a key-agreement protocol by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe that is designed to resist quantum computer attacks.
The Commercial National Security Algorithm Suite (CNSA) is a set of cryptographic algorithms promulgated by the National Security Agency as a replacement for NSA Suite B Cryptography algorithms. It serves as the cryptographic base to protect US National Security Systems information up to the top secret level, while the NSA plans for a transition to quantum-resistant cryptography.
Kyber is a key encapsulation mechanism (KEM) designed to be resistant to cryptanalytic attacks with future powerful quantum computers. It is used to establish a shared secret between two communicating parties without an (IND-CCA2) attacker in the transmission system being able to decrypt it. This asymmetric cryptosystem uses a variant of the learning with errors lattice problem as its basic trapdoor function. It won the NIST competition for the first post-quantum cryptography (PQ) standard. NIST calls its draft standard Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM).
Falcon is a post-quantum signature scheme selected by the NIST at the fourth round of the post-quantum standardisation process. It was designed by Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. It relies on the hash-and-sign technique over the Gentry, Peikert, and Vaikuntanathan framework over NTRU lattices. The name Falcon is an acronym for Fast Fourier lattice-based compact signatures over NTRU.