Project by NIST to standardize post-quantum cryptography
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.
Academic research on the potential impact of quantum computing dates back to at least 2001.[5] 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.[6] 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.[7]
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).
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.[52] 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.[53]
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.
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]
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]
SIKE: by Wouter Castryck and Thomas Decru on a classical computer[63]
Additional Digital Signature Schemes Round One[edit]
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)
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])
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])
^"qTESLA". Microsoft Research. Archived from the original on 31 December 2022. Retrieved 4 March 2024.
^ ab"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.
^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. ISBN978-3-319-97915-1.
^Carrier, Kevin; Hatey, Valérian; Tillich, Jean-Pierre (5 December 2023). "Projective Space Stern Decoding and Application to SDitH". arXiv:2312.02607 [cs.IT].