NIST Post-Quantum Cryptography Standardization explained

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

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

Under consideration were:[9]
(strikethrough means it had been withdrawn)

TypePKE/KEMSignatureSignature & PKE/KEM
Lattice
  • Compact LWE
  • CRYSTALS-Kyber
  • Ding Key Exchange
  • EMBLEM and R.EMBLEM
  • FrodoKEM
  • HILA5 (withdrawn and merged into Round5)
  • KCL (pka OKCN/AKCN/CNKE)
  • KINDI
  • LAC
  • LIMA
  • Lizard
  • LOTUS
  • NewHope
  • NTRUEncrypt
  • NTRU-HRSS-KEM
  • NTRU Prime
  • Odd Manhattan
  • Round2 (withdrawn and merged into Round5)
  • Round5 (merger of Round2 and Hila5, announced 4 August 2018)
  • SABER
  • Three Bears
  • Titanium
Code-based
  • BIG QUAKE
  • BIKE
  • Classic McEliece + NTS-KEM
  • DAGS
  • Edon-K
  • HQC
  • LAKE (withdrawn and merged into ROLLO)
  • LEDAkem
  • LEDApkc
  • Lepton
  • LOCKER (withdrawn and merged into ROLLO)
  • McNie
  • NTS-KEM
  • ROLLO (merger of Ouroboros-R, LAKE and LOCKER)
  • Ouroboros-R (withdrawn and merged into ROLLO)
  • QC-MDPC KEM
  • Ramstake
  • RLCE-KEM
  • RQC
  • pqsigRM
  • RaCoSS
  • RankSign
Hash-based
  • Gravity-SPHINCS
  • SPHINCS+
Multivariate
  • CFPKM
  • Giophantus
  • DualModeMS
  • GeMSS
  • Gui
  • HiMQ-3
  • LUOV
  • MQDSS
  • Rainbow
  • SRTPI
  • DME
Braid group
  • WalnutDSA
Supersingular elliptic curve isogeny
Satirical submission
Other
  • Guess Again
  • HK17
  • Mersenne-756839
  • RVB
  • Picnic

Round one submissions published attacks

Round two

Candidates moving on to the second round were announced on January 30, 2019. They are:[30]

TypePKE/KEMSignature
Lattice
Code-based
Hash-based
Multivariate
Supersingular elliptic curve isogeny
Zero-knowledge proofs

Round three

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.

On June 7–9, 2021, NIST conducted the third PQC standardization conference, virtually.[54] 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

TypePKE/KEMSignature
Lattice
Code-based
Multivariate
  • Rainbow

Alternate candidates

TypePKE/KEMSignature
Lattice
  • FrodoKEM
  • NTRU Prime
Code-based
Hash-based
  • SPHINCS+
Multivariate
  • GeMSS
Supersingular elliptic curve isogeny
Zero-knowledge proofs
  • Picnic

Intellectual property concerns

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.[55]

Round three submissions published attacks

Adaptations

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.[57]
  • FALCON: side channel attack by . A masking may be added in order to resist the attack. This adaptation affects performance and should be considered while standardizing.[58]
  • Selected Algorithms 2022

    On July 5, 2022, NIST announced the first group of winners from its six-year competition.[59] [60]

    TypePKE/KEMSignature
    Lattice
    Hash-based

    Round four

    On July 5, 2022, NIST announced four candidates for PQC Standardization Round 4.[61]

    TypePKE/KEM
    Code-based
    Supersingular elliptic curve isogeny

    Round four submissions published attacks

    First release

    On August 13, 2024, NIST released final versions of its first three Post Quantum Crypto Standards. 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:

    Additional Digital Signature Schemes Round One

    NIST received 50 submissions and deemed 40 to be complete and proper according to the submission requirements.[64] Under consideration are:[65]
    (strikethrough means it has been withdrawn)

    TypeSignature
    Lattice
    Code-based
    MPC-in-the-Head
    Multivariate
    • 3WISE ("the submitter agrees that the scheme is insecure, but prefers to not withdraw in the hope that studying the scheme will advance cryptanalysis"[82])
    • Biscuit[83]
    • DME-Sign ("Our first impression is that the attack works and we are checking the details of the attack .We are implementing a variant of the DME that may resist the attack but we have to verify it."[84])
    • HPPC
    • MAYO[85]
    • PROV[86]
    • QR-UOV[87]
    • SNOVA[88]
    • TUOV[89]
    • UOV[90]
    • VOX[91]
    Supersingular elliptic curve isogeny
    Symmetric-based
    • AIMer[93]
    • Ascon-Sign
    • FAEST[94]
    • SPHINCS-alpha
    Other
    • ALTEQ[95]
    • eMLE-Sig 2.0
    • KAZ-SIGN
    • Preon
    • Xifrat1-Sign.I

    Additional signature round one submissions published attacks

    See also

    External links

    Notes and References

    1. Web site: Post-Quantum Cryptography PQC. 3 January 2017.
    2. Web site: Post-Quantum Cryptography Standardization – Post-Quantum Cryptography . 3 January 2017. Csrc.nist.gov. 31 January 2019.
    3. The Future Is Now: Spreading the Word About Post-Quantum Cryptography. NIST . 24 November 2020. Moody . Dustin .
    4. Web site: Final Submission received . 2017-12-29 . https://web.archive.org/web/20171229232437/https://post-quantum.ch/ . 2017-12-29 . dead .
    5. https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards NIST Releases First 3 Finalized Post-Quantum Encryption Standards
    6. Web site: Hong. Zhu. 2001. Survey of Computational Assumptions Used in Cryptography Broken or Not by Shor's Algorithm.
    7. Web site: NIST Released NISTIR 8105, Report on Post-Quantum Cryptography. 21 December 2016. 5 November 2019.
    8. NIST Asks Public to Help Future-Proof Electronic Information. NIST . 20 December 2016. 5 November 2019.
    9. Web site: Round 1 Submissions – Post-Quantum Cryptography – CSRC. Information Technology Laboratory. Computer Security Division. 3 January 2017. Csrc.nist.gov. 31 January 2019.
    10. Web site: qTESLA team . Efficient and post-quantum secure lattice-based signature scheme . dead . https://web.archive.org/web/20231209220840/https://qtesla.org/ . 2023-12-09 . 2024-03-04 . qTESLA.org.
    11. Web site: qTESLA . live . https://web.archive.org/web/20221231072042/https://www.microsoft.com/en-us/research/project/qtesla/ . 2022-12-31 . 2024-03-04 . Microsoft Research . en-US.
    12. RSA using 231 4096-bit primes for a total key size of 1 TiB. "Key almost fits on a hard drive"Web site: McBits and Post-Quantum RSA . Bernstein . Daniel . Daniel J. Bernstein . 2010-05-28 . 2019-12-10.
    13. Web site: Post-quantum RSA . Bernstein . Daniel . Daniel J. Bernstein . Heninger . Nadia . 2017-04-19 . 2019-12-10.
    14. Web site: Dear all, the following Python script quickly recovers the message from a given "Guess Again" ciphertext without knowledge of the private key. Csrc.nist.gov. 30 January 2019.
    15. Web site: Fast key recovery attack against the "RVB" submission to #NISTPQC: t .... Computes private from public key.. Lorenz. Panny. 25 December 2017. Twitter. 31 January 2019.
    16. Web site: Comments on RaCoSS . 2018-01-04 . https://web.archive.org/web/20171226100156/https://helaas.org/racoss/ . 2017-12-26 . dead .
    17. Web site: Comments on HK17 . 2018-01-04 . https://web.archive.org/web/20180105070112/https://helaas.org/hk17/ . 2018-01-05 . dead .
    18. Web site: Dear all, We have broken SRTPI under CPA and TPSig under KMA.. Csrc.nist.gov. 30 January 2019.
    19. Beullens. Ward. Blackburn. Simon R.. 2018. Practical attacks against the Walnut digital signature scheme. Cryptology ePrint Archive.
    20. Kotov. Matvei . Menshov . Anton. Alexander. Ushakov . 2018. An attack on the walnut digital signature algorithm. Cryptology ePrint Archive.
    21. Yu. Yang. Ducas . Léo . 2018. Learning strikes again: the case of the DRS signature scheme. Cryptology ePrint Archive.
    22. Barelli . Elise . Couvreur. Alain . 2018. An efficient structural attack on NIST submission DAGS. 1805.05429. cs.CR .
    23. Lequesne . Matthieu . Tillich. Jean-Pierre . 2018. Attack on the Edon-K Key Encapsulation Mechanism. 1802.06157. cs.CR .
    24. Couvreur. Alain . Lequesne. Matthieu . Tillich. Jean-Pierre. 2018. Recovering short secret keys of RLCE in polynomial time. 1805.11489. cs.CR .
    25. Hila5 Pindakaas: On the CCA security of lattice-based encryption with error correction. Bernstein. Daniel J.. Groot Bruinderink. Leon. Tanja. Lange. Lorenz. Lange. Cryptology ePrint Archive . 2017.
    26. Web site: Official Comments. 13 September 2018. Csrc.nist.gov.
    27. Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme. 1804.02556. Debris-Alazard. Thomas. Tillich. Jean-Pierre. cs.CR. 2018.
    28. Web site: I am afraid the parameters in this proposal have at most 4 to 6-bits security under the Information Set Decoding (ISD) attack.. Csrc.nist.gov. 30 January 2019.
    29. Book: Key Recovery Attack on McNie Based on Low Rank Parity Check Codes and Its Reparation. Terry Shue Chien. Advances in Information and Computer Security. 11049. Lau. Chik How. Tan. Atsuo. Inomata. Kan. Yasuda. 31 January 2019. Springer International Publishing. 19–34. 10.1007/978-3-319-97916-8_2. Lecture Notes in Computer Science. 978-3-319-97915-1.
    30. Web site: Round 2 Submissions – Post-Quantum Cryptography – CSRC. Information Technology Laboratory. Computer Security Division. 3 January 2017. Csrc.nist.gov. 31 January 2019.
    31. Web site: CRYSTALS. Peter. Schwabe. Pq-crystals.org. 31 January 2019.
    32. Web site: FrodoKEM. Frodokem.org. 31 January 2019.
    33. Web site: NewHope. Peter. Schwabe. Newhopecrypto.org. 31 January 2019.
    34. Web site: NIST Post Quantum Crypto Submission . 2017-12-29 . https://web.archive.org/web/20171229114632/https://www.onboardsecurity.com/nist-post-quantum-crypto-submission . 2017-12-29 . dead .
    35. Web site: NTRU Prime: Intro . 2019-01-30 . https://web.archive.org/web/20190901185114/https://ntruprime.cr.yp.to/ . 2019-09-01 . dead .
    36. Web site: Google Groups. Groups.google.com. 31 January 2019.
    37. Web site: SABER. 17 June 2019.
    38. Web site: ThreeBears. SourceForge.net. 31 January 2019.
    39. Web site: Falcon. Falcon. 26 June 2019.
    40. Web site: BIKE – Bit Flipping Key Encapsulation. Bikesuite.org. 31 January 2019.
    41. Web site: HQC. Pqc-hqc.org. 31 January 2019.
    42. Web site: LEDAkem Key Encapsulation Module. Ledacrypt.org. 31 January 2019.
    43. Web site: LEDApkc Public Key Cryptosystem. Ledacrypt.org. 31 January 2019.
    44. Web site: NTS-Kem . 2017-12-29 . https://web.archive.org/web/20171229103229/https://nts-kem.io/ . 2017-12-29 . dead .
    45. Web site: ROLLO. Pqc-rollo.org. 31 January 2019.
    46. Web site: RQC. Pqc-rqc.org. 31 January 2019.
    47. Web site: Sphincs . Sphincs.org . 2023-06-19.
    48. Web site: GeMSS . 2019-01-30 . https://web.archive.org/web/20190131040055/https://www-polsys.lip6.fr/Links/NIST/GeMSS.html . 2019-01-31 . dead .
    49. Web site: LUOV -- An MQ signature scheme. 22 January 2020.
    50. Web site: MQDSS post-quantum signature. Mqdss.org. 31 January 2019.
    51. Web site: SIKE – Supersingular Isogeny Key Encapsulation. Sike.org. 31 January 2019.
    52. Web site: Picnic. A Family of Post-Quantum Secure Digital Signature Algorithms. microsoft.github.io. 26 February 2019.
    53. Web site: Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process . 2020 . 10.6028/NIST.IR.8309 . 2020-07-23. 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 . 243755462 . free .
    54. Web site: Computer Security Division. Information Technology Laboratory. 2021-02-10. Third PQC Standardization Conference CSRC. 2021-07-06. CSRC NIST. EN-US.
    55. Web site: Submission Requirements and Evaluation Criteria.
    56. Beullens. Ward. 2022. Breaking Rainbow Takes a Weekend on a Laptop. Eprint.iacr.org.
    57. Grubbs. Paul. Maram. Varun. Paterson. Kenneth G.. 2021. Anonymous, Robust Post-Quantum Public Key Encryption. Cryptology ePrint Archive .
    58. Karabulut. Emre. Aysu. Aydin. 2021. Falcon Down: Breaking Falcon Post-Quantum Signature Scheme through Side-Channel Attacks. Cryptology ePrint Archive .
    59. 2022-07-05. NIST Announces First Four Quantum-Resistant Cryptographic Algorithms. 2022-07-09. NIST. EN-US.
    60. Web site: 2022-07-05. Selected Algorithms 2022. 2022-07-09. CSRC NIST. EN-US.
    61. Web site: 2022-07-05. Round 4 Submissions. 2022-07-09. CSRC NIST. EN-US.
    62. Web site: SIKE Team - Foreword and postscript.
    63. Web site: Goodin . Dan . Post-quantum encryption contender is taken out by single-core PC and 1 hour . Ars Technica . 2 August 2022 . 6 August 2022.
    64. Web site: Moody . Dustin . 17 July 2023 . Onramp submissions are posted! .
    65. Web site: Digital Signature Schemes. csrc.nist.gov. 29 August 2022 . 17 July 2023.
    66. Web site: SMAUG & HAETAE - HAETAE .
    67. Web site: Hufu .
    68. Web site: RACCOON – Not just a signature, a whole family of it ! .
    69. Web site: masksign/raccoon: Raccoon Signature Scheme -- Reference Code . .
    70. Web site: Squirrels - Introduction .
    71. Web site: CROSS crypto .
    72. Web site: FuLeeca: A Lee-based Signature Scheme - Lehrstuhl für Nachrichtentechnik .
    73. Web site: LESS project .
    74. Web site: MEDS .
    75. Web site: WAVE .
    76. Web site: MIRA .
    77. Web site: MiRitH .
    78. Web site: MQOM .
    79. Web site: PERK .
    80. Web site: RYDE .
    81. Web site: SD-in-the-Head .
    82. Web site: Smith-Tone . Daniel . 17 July 2023 . OFFICIAL COMMENT: 3WISE .
    83. Web site: Home .
    84. Web site: OFFICIAL COMMENT: DME Key Recovery Attack . 2023-09-10 . groups.google.com.
    85. Web site: MAYO .
    86. Web site: PROV .
    87. Web site: QR-UOV .
    88. Web site: SNOVA . snova.pqclab.org. 2023-09-23 .
    89. Web site: TUOV .
    90. Web site: UOV .
    91. Web site: VOX .
    92. Web site: SQIsign .
    93. Web site: AIMer Signature .
    94. Web site: Come and join the FAEST FAEST Signature Algorithm .
    95. Web site: ALTEQ .
    96. Web site: Tibouchi . Mehdi . 17 July 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: EagleSign .
    97. Web site: Bernstein . D.J. . 17 July 2023 . OFFICIAL COMMENT: KAZ-SIGN .
    98. Web site: Fluhrer . Scott . 17 July 2023 . KAZ-SIGN .
    99. Web site: Panny . Lorenz . 17 July 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: Xifrat1-Sign.I .
    100. Web site: Tibouchi . Mehdi . 18 July 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: EagleSign .
    101. Web site: Beullens . Ward . 18 July 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: HPPC .
    102. Web site: Perlner . Ray . 21 July 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: HPPC .
    103. Web site: Saarinen . Markku-Juhani O. . 18 July 2023 . OFFICIAL COMMENT: ALTEQ .
    104. Web site: Bouillaguet . Charles . 19 July 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: Biscuit .
    105. Web site: Niederhagen . Ruben . 19 July 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: MEDS .
    106. Web site: van Woerden . Wessel . 20 July 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: FuLeeca .
    107. Web site: Persichetti . Edoardo . 21 July 2023 . OFFICIAL COMMENT: LESS .
    108. Web site: Saarinen . Markku-Juhani O. . Round 1 (Additional Signatures) OFFICIAL COMMENT: DME-Sign .
    109. Web site: OFFICIAL COMMENT: DME Key Recovery Attack . 2023-09-10 . groups.google.com.
    110. Web site: van Woerden . Wessel . Jul 25, 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: EHTv3 .
    111. Web site: Suhl . Adam . Jul 29, 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: EHT .
    112. Web site: VASSEUR . Valentin . Jul 29, 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM .
    113. Web site: Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM . 2023-09-30 . groups.google.com.
    114. Web site: Saarinen . Markku-Juhani O. . Jul 27, 2023 . Buffer overflows in HAETAE / On crypto vs implementation errors. .
    115. Web site: Saarinen . Markku-Juhani O. . Jul 29, 2023 . HuFu: Big-flipping forgeries and buffer overflows .
    116. Web site: Carrier . Kevin . Aug 3, 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: SDitH .
    117. Carrier . Kevin . Hatey . Valérian . Tillich . Jean-Pierre . 5 Dec 2023 . Projective Space Stern Decoding and Application to SDitH . cs.IT . 2312.02607.
    118. Web site: Furue . Hiroki . Aug 28, 2023 . Round 1 (Additional Signatures) OFFICIAL COMMENT: VOX .
    119. Liu . Fukang . Mahzoun . Mohammad . Øygarden . Morten . Meier . Willi . Algebraic Attacks on RAIN and AIM Using Equivalent Representations . IACR ePrint . 10 November 2023 . 2023/1133.