NIST Post-Quantum Cryptography Standardization
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]
Background
[edit]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).
Round one
[edit]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 |
|
|
Round one submissions published attacks
[edit]- Guess Again by Lorenz Panny [17]
- RVB by Lorenz Panny[18]
- RaCoSS by Daniel J. Bernstein, Andreas Hülsing, Tanja Lange and Lorenz Panny[19]
- HK17 by Daniel J. Bernstein and Tanja Lange[20]
- SRTPI by Bo-Yin Yang[21]
- WalnutDSA
- DRS by Yang Yu and Léo Ducas [24]
- DAGS by Elise Barelli and Alain Couvreur[25]
- Edon-K by Matthieu Lequesne and Jean-Pierre Tillich[26]
- RLCE by Alain Couvreur, Matthieu Lequesne, and Jean-Pierre Tillich[27]
- Hila5 by Daniel J. Bernstein, Leon Groot Bruinderink, Tanja Lange and Lorenz Panny[28]
- Giophantus by Ward Beullens, Wouter Castryck and Frederik Vercauteren[29]
- RankSign by Thomas Debris-Alazard and Jean-Pierre Tillich [30]
- McNie by Philippe Gaborit;[31] Terry Shue Chien Lau and Chik How Tan [32]
Round two
[edit]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 |
|
Round three
[edit]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.
Finalists
[edit]Type | PKE/KEM | Signature |
---|---|---|
Lattice | ||
Code-based |
|
|
Multivariate |
Alternate candidates
[edit]Type | PKE/KEM | Signature |
---|---|---|
Lattice |
|
|
Code-based | ||
Hash-based |
| |
Multivariate |
| |
Supersingular elliptic curve isogeny | ||
Zero-knowledge proofs |
|
Intellectual property concerns
[edit]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]
Round three submissions published attacks
[edit]- Rainbow: by Ward Beullens on a classical computer[57]
Adaptations
[edit]During this round, some candidates have shown to be vulnerable to some attack vectors. It forces these candidates to adapt accordingly:
- CRYSTAL-Kyber and SABER
- may change the nested hashes used in their proposals in order for their security claims to hold.[58]
- FALCON
- side channel attack by . A masking may be added in order to resist the attack. This adaptation affects performance and should be considered whilst standardizing.[59]
Selected Algorithms 2022
[edit]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 |
Round four
[edit]On July 5, 2022, NIST announced four candidates for PQC Standardization Round 4.[62]
Type | PKE/KEM |
---|---|
Code-based | |
Supersingular elliptic curve isogeny |
Round four submissions published attacks
[edit]- SIKE: by Wouter Castryck and Thomas Decru on a classical computer[64]
First release
[edit]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.
Additional Digital Signature Schemes Round One
[edit]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 |
|
Additional signature round one submissions published attacks
[edit]- 3WISE by Daniel Smith-Tone[83]
- EagleSign by Mehdi Tibouchi[97]
- KAZ-SIGN by Daniel J. Bernstein;[98] Scott Fluhrer[99]
- Xifrat1-Sign.I by Lorenz Panny[100]
- eMLE-Sig 2.0 by Mehdi Tibouchi[101]
- HPPC by Ward Beullens[102];Pierre Briaud, Maxime Bros, and Ray Perlner[103]
- ALTEQ by Markku-Juhani O. Saarinen[104] (implementation only?)
- Biscuit by Charles Bouillaguet[105]
- MEDS by Markku-Juhani O. Saarinen and Ward Beullens[106] (implementation only)
- FuLeeca by Felicitas Hörmann and Wessel van Woerden[107]
- LESS by the LESS team (implementation only)[108]
- DME-Sign by Markku-Juhani O. Saarinen[109] (implementation only?); Pierre Briaud, Maxime Bros, Ray Perlner, and Daniel Smith-Tone[110]
- EHTv3 by Eamonn Postlethwaite and Wessel van Woerden;[111] Keegan Ryan and Adam Suhl[112]
- Enhanced pqsigRM by Thomas Debris-Alazard, Pierre Loisel and Valentin Vasseur;[113] Pierre Briaud, Maxime Bros, Ray Perlner and Daniel Smith-Tone[114]
- HAETAE by Markku-Juhani O. Saarinen[115] (implementation only?)
- HuFu by Markku-Juhani O. Saarinen[116]
- SDitH by Kevin Carrier and Jean-Pierre Tillich;[117] Kevin Carrier, Valérian Hatey, and Jean-Pierre Tillich[118]
- VOX by Hiroki Furue and Yasuhiko Ikematsu[119]
- AIMer by Fukang Liu, Mohammad Mahzoun, Morten Øygarden, Willi Meier[120]
- SNOVA by Yasuhiko Ikematsu and Rika Akiyama[121]
- PROV by Ludovic Perret, and River Moreira Ferreira[122] (implementation only)
See also
[edit]- Advanced Encryption Standard process
- CAESAR Competition – Competition to design authenticated encryption schemes
- Lattice-based cryptography
- NIST hash function competition
References
[edit]- ^ "Post-Quantum Cryptography PQC". 3 January 2017.
- ^ "Post-Quantum Cryptography Standardization – Post-Quantum Cryptography". Csrc.nist.gov. 3 January 2017. Retrieved 31 January 2019.
- ^ Moody, Dustin (24 November 2020). "The Future Is Now: Spreading the Word About Post-Quantum Cryptography". NIST.
- ^ "Final Submission received". Archived from the original on 29 December 2017. Retrieved 29 December 2017.
- ^ a b NIST Releases First 3 Finalized Post-Quantum Encryption Standards, NIST, August 13, 2024
- ^ Hong, Zhu (2001). "Survey of Computational Assumptions Used in Cryptography Broken or Not by Shor's Algorithm" (PDF).
- ^ "NIST Released NISTIR 8105, Report on Post-Quantum Cryptography". 21 December 2016. Retrieved 5 November 2019.
- ^ "NIST Asks Public to Help Future-Proof Electronic Information". NIST. 20 December 2016. Retrieved 5 November 2019.
- ^ Computer Security Division, Information Technology Laboratory (3 January 2017). "Round 1 Submissions – Post-Quantum Cryptography – CSRC". Csrc.nist.gov. Retrieved 31 January 2019.
- ^ a b c "NIST Post Quantum Crypto Submission". Archived from the original on 29 December 2017. Retrieved 29 December 2017.
- ^ a b "Google Groups". Groups.google.com. Retrieved 31 January 2019.
- ^ qTESLA team. "Efficient and post-quantum secure lattice-based signature scheme". qTESLA.org. Archived from the original on 9 December 2023. Retrieved 4 March 2024.
- ^ "qTESLA". Microsoft Research. Archived from the original on 31 December 2022. Retrieved 4 March 2024.
- ^ a b "ROLLO". Pqc-rollo.org. Retrieved 31 January 2019.
- ^ RSA using 231 4096-bit primes for a total key size of 1 TiB. "Key almost fits on a hard drive" Bernstein, Daniel (28 May 2010). "McBits and Post-Quantum RSA" (PDF). Retrieved 10 December 2019.
- ^ Bernstein, Daniel; Heninger, Nadia (19 April 2017). "Post-quantum RSA" (PDF). Retrieved 10 December 2019.
- ^ "Dear all, the following Python script quickly recovers the message from a given "Guess Again" ciphertext without knowledge of the private key" (PDF). Csrc.nist.gov. Retrieved 30 January 2019.
- ^ Panny, Lorenz (25 December 2017). "Fast key recovery attack against the "RVB" submission to #NISTPQC: t .... Computes private from public key". Twitter. Retrieved 31 January 2019.
- ^ "Comments on RaCoSS". Archived from the original on 26 December 2017. Retrieved 4 January 2018.
- ^ "Comments on HK17". Archived from the original on 5 January 2018. Retrieved 4 January 2018.
- ^ "Dear all, We have broken SRTPI under CPA and TPSig under KMA" (PDF). Csrc.nist.gov. Retrieved 30 January 2019.
- ^ Beullens, Ward; Blackburn, Simon R. (2018). "Practical attacks against the Walnut digital signature scheme". Cryptology ePrint Archive.
- ^ Kotov, Matvei; Menshov, Anton; Ushakov, Alexander (2018). "An attack on the walnut digital signature algorithm". Cryptology ePrint Archive.
- ^ Yu, Yang; Ducas, Léo (2018). "Learning strikes again: the case of the DRS signature scheme". Cryptology ePrint Archive.
- ^ Barelli, Elise; Couvreur, Alain (2018). "An efficient structural attack on NIST submission DAGS". arXiv:1805.05429 [cs.CR].
- ^ Lequesne, Matthieu; Tillich, Jean-Pierre (2018). "Attack on the Edon-K Key Encapsulation Mechanism". arXiv:1802.06157 [cs.CR].
- ^ Couvreur, Alain; Lequesne, Matthieu; Tillich, Jean-Pierre (2018). "Recovering short secret keys of RLCE in polynomial time". arXiv:1805.11489 [cs.CR].
- ^ Bernstein, Daniel J.; Groot Bruinderink, Leon; Lange, Tanja; Lange, Lorenz (2017). "Hila5 Pindakaas: On the CCA security of lattice-based encryption with error correction". Cryptology ePrint Archive.
- ^ "Official Comments" (PDF). Csrc.nist.gov. 13 September 2018.
- ^ Debris-Alazard, Thomas; Tillich, Jean-Pierre (2018). "Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme". arXiv:1804.02556 [cs.CR].
- ^ "I am afraid the parameters in this proposal have at most 4 to 6-bits security under the Information Set Decoding (ISD) attack" (PDF). Csrc.nist.gov. Retrieved 30 January 2019.
- ^ Lau, Terry Shue Chien; Tan, Chik How (31 January 2019). "Key Recovery Attack on McNie Based on Low Rank Parity Check Codes and Its Reparation". In Inomata, Atsuo; Yasuda, Kan (eds.). Advances in Information and Computer Security. Lecture Notes in Computer Science. Vol. 11049. Springer International Publishing. pp. 19–34. doi:10.1007/978-3-319-97916-8_2. ISBN 978-3-319-97915-1.
- ^ Computer Security Division, Information Technology Laboratory (3 January 2017). "Round 2 Submissions – Post-Quantum Cryptography – CSRC". Csrc.nist.gov. Retrieved 31 January 2019.
- ^ a b Schwabe, Peter. "CRYSTALS". Pq-crystals.org. Retrieved 31 January 2019.
- ^ "FrodoKEM". Frodokem.org. Retrieved 31 January 2019.
- ^ Schwabe, Peter. "NewHope". Newhopecrypto.org. Retrieved 31 January 2019.
- ^ "NTRU Prime: Intro". Archived from the original on 1 September 2019. Retrieved 30 January 2019.
- ^ "SABER". Retrieved 17 June 2019.
- ^ "ThreeBears". SourceForge.net. Retrieved 31 January 2019.
- ^ "Falcon". Falcon. Retrieved 26 June 2019.
- ^ "BIKE – Bit Flipping Key Encapsulation". Bikesuite.org. Retrieved 31 January 2019.
- ^ "HQC". Pqc-hqc.org. Retrieved 31 January 2019.
- ^ "LEDAkem Key Encapsulation Module". Ledacrypt.org. Retrieved 31 January 2019.
- ^ "LEDApkc Public Key Cryptosystem". Ledacrypt.org. Retrieved 31 January 2019.
- ^ "NTS-Kem". Archived from the original on 29 December 2017. Retrieved 29 December 2017.
- ^ "RQC". Pqc-rqc.org. Retrieved 31 January 2019.
- ^ "Sphincs". Sphincs.org. Retrieved 19 June 2023.
- ^ "GeMSS". Archived from the original on 31 January 2019. Retrieved 30 January 2019.
- ^ "LUOV -- An MQ signature scheme". Retrieved 22 January 2020.
- ^ "MQDSS post-quantum signature". Mqdss.org. Retrieved 31 January 2019.
- ^ "SIKE – Supersingular Isogeny Key Encapsulation". Sike.org. Retrieved 31 January 2019.
- ^ "Picnic. A Family of Post-Quantum Secure Digital Signature Algorithms". microsoft.github.io. Retrieved 26 February 2019.
- ^ Moody, Dustin; Alagic, Gorjan; Apon, Daniel C.; Cooper, David A.; Dang, Quynh H.; Kelsey, John M.; Liu, Yi-Kai; Miller, Carl A.; Peralta, Rene C.; Perlner, Ray A.; Robinson, Angela Y.; Smith-Tone, Daniel C.; Alperin-Sheriff, Jacob (2020). "Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process". doi:10.6028/NIST.IR.8309. S2CID 243755462. Retrieved 23 July 2020.
- ^ Third PQC Standardization Conference - Session I Welcome/Candidate Updates, 10 June 2021, retrieved 6 July 2021
- ^ Computer Security Division, Information Technology Laboratory (10 February 2021). "Third PQC Standardization Conference | CSRC". CSRC | NIST. Retrieved 6 July 2021.
- ^ "Submission Requirements and Evaluation Criteria" (PDF).
- ^ Beullens, Ward (2022). "Breaking Rainbow Takes a Weekend on a Laptop" (PDF). Eprint.iacr.org.
- ^ Grubbs, Paul; Maram, Varun; Paterson, Kenneth G. (2021). "Anonymous, Robust Post-Quantum Public Key Encryption". Cryptology ePrint Archive.
- ^ Karabulut, Emre; Aysu, Aydin (2021). "Falcon Down: Breaking Falcon Post-Quantum Signature Scheme through Side-Channel Attacks". Cryptology ePrint Archive.
- ^ "NIST Announces First Four Quantum-Resistant Cryptographic Algorithms". NIST. 5 July 2022. Retrieved 9 July 2022.
- ^ "Selected Algorithms 2022". CSRC | NIST. 5 July 2022. Retrieved 9 July 2022.
- ^ "Round 4 Submissions". CSRC | NIST. 5 July 2022. Retrieved 9 July 2022.
- ^ "SIKE Team - Foreword and postscript" (PDF).
- ^ Goodin, Dan (2 August 2022). "Post-quantum encryption contender is taken out by single-core PC and 1 hour". Ars Technica. Retrieved 6 August 2022.
- ^ Moody, Dustin (17 July 2023). "Onramp submissions are posted!".
- ^ "Digital Signature Schemes". csrc.nist.gov. 29 August 2022. Retrieved 17 July 2023.
- ^ "SMAUG & HAETAE - HAETAE".
- ^ "Hufu".
- ^ "RACCOON – Not just a signature, a whole family of it !".
- ^ "masksign/raccoon: Raccoon Signature Scheme -- Reference Code". GitHub.
- ^ "Squirrels - Introduction".
- ^ "CROSS crypto".
- ^ "FuLeeca: A Lee-based Signature Scheme - Lehrstuhl für Nachrichtentechnik".
- ^ "LESS project".
- ^ "MEDS".
- ^ "WAVE".
- ^ "MIRA".
- ^ "MiRitH".
- ^ "MQOM".
- ^ "PERK".
- ^ "RYDE".
- ^ "SD-in-the-Head".
- ^ a b Smith-Tone, Daniel (17 July 2023). "OFFICIAL COMMENT: 3WISE".
- ^ "Home".
- ^ "OFFICIAL COMMENT: DME Key Recovery Attack". groups.google.com. Retrieved 10 September 2023.
- ^ "MAYO".
- ^ "PROV".
- ^ "QR-UOV".
- ^ "SNOVA". snova.pqclab.org. Retrieved 23 September 2023.
- ^ "TUOV".
- ^ "UOV".
- ^ "VOX".
- ^ "SQIsign".
- ^ "AIMer Signature".
- ^ "Come and join the FAEST | FAEST Signature Algorithm".
- ^ "ALTEQ".
- ^ Tibouchi, Mehdi (17 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: EagleSign".
- ^ Bernstein, D.J. (17 July 2023). "OFFICIAL COMMENT: KAZ-SIGN".
- ^ Fluhrer, Scott (17 July 2023). "KAZ-SIGN".
- ^ Panny, Lorenz (17 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: Xifrat1-Sign.I".
- ^ Tibouchi, Mehdi (18 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: EagleSign".
- ^ Beullens, Ward (18 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: HPPC".
- ^ Perlner, Ray (21 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: HPPC".
- ^ Saarinen, Markku-Juhani O. (18 July 2023). "OFFICIAL COMMENT: ALTEQ".
- ^ Bouillaguet, Charles (19 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: Biscuit".
- ^ Niederhagen, Ruben (19 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: MEDS".
- ^ van Woerden, Wessel (20 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: FuLeeca".
- ^ Persichetti, Edoardo (21 July 2023). "OFFICIAL COMMENT: LESS".
- ^ Saarinen, Markku-Juhani O. "Round 1 (Additional Signatures) OFFICIAL COMMENT: DME-Sign".
- ^ "OFFICIAL COMMENT: DME Key Recovery Attack". groups.google.com. Retrieved 10 September 2023.
- ^ van Woerden, Wessel (25 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: EHTv3".
- ^ Suhl, Adam (29 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: EHT".
- ^ VASSEUR, Valentin (29 July 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM".
- ^ "Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM". groups.google.com. Retrieved 30 September 2023.
- ^ Saarinen, Markku-Juhani O. (27 July 2023). "Buffer overflows in HAETAE / On crypto vs implementation errors".
- ^ Saarinen, Markku-Juhani O. (29 July 2023). "HuFu: Big-flipping forgeries and buffer overflows".
- ^ Carrier, Kevin (3 August 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: SDitH".
- ^ Carrier, Kevin; Hatey, Valérian; Tillich, Jean-Pierre (5 December 2023). "Projective Space Stern Decoding and Application to SDitH". arXiv:2312.02607 [cs.IT].
- ^ Furue, Hiroki (28 August 2023). "Round 1 (Additional Signatures) OFFICIAL COMMENT: VOX".
- ^ Liu, Fukang; Mahzoun, Mohammad; Øygarden, Morten; Meier, Willi (10 November 2023). "Algebraic Attacks on RAIN and AIM Using Equivalent Representations". IACR ePrint (2023/1133).
- ^ Ikematsu, Yasuhiko; Akiyama, Rika (2024), Revisiting the security analysis of SNOVA, retrieved 28 January 2024
- ^ Ferreira, River Moreira; Perret, Ludovic (2024), Polynomial-Time Key-Recovery Attack on the ${\tt NIST}$ Specification of ${\tt PROV}$, retrieved 4 April 2024