Status report on the third round of the NIST post-quantum cryptography standardization process
DOI:
https://doi.org/10.30837/rt.2022.3.210.05Keywords:
post-quantum cryptography, standardization, NIST, electronic signature, key transportAbstract
In recent years, there has been steady progress in the creation of quantum computers. If large-scale quantum computers are implemented, they will threaten the security of many widely used public-key cryptosystems. Key-establishment schemes and digital signatures based on factorization, discrete logarithms, and elliptic curve cryptography will be most affected. Symmetric cryptographic primitives such as block ciphers and hash functions will be broken only slightly. As a result, there has been an intensification of research on finding public-key cryptosystems that would be secure against cryptanalysts with both quantum and classical computers. This area is often called post-quantum cryptography (PQC), or sometimes quantum-resistant cryptography. The goal is to design schemes that can be deployed in existing communication networks and protocols without significant changes. The National Institute of Standards and Technology is in the process of selecting one or more public-key cryptographic algorithms through an open competition. New public-key cryptography standards will define one or more additional digital signatures, public-key encryption, and key-establishment algorithms. It is assumed that these algorithms will be able to protect confidential information well in the near future, including after the advent of quantum computers. After three rounds of evaluation and analysis, NIST has selected the first algorithms that will be standardized as a result of the PQC standardization process. The purpose of this article is to review and analyze the state of NIST's post-quantum cryptography standardization evaluation and selection process. The article summarizes each of the 15 candidate algorithms from the third round and identifies the algorithms selected for standardization, as well as those that will continue to be evaluated in the fourth round of analysis. Although the third round is coming to an end and NIST will begin developing the first PQC standards, standardization efforts in this area will continue for some time. This should not be interpreted as meaning that users should wait to adopt post-quantum algorithms. NIST looks forward to the rapid implementation of these first standardized algorithms and will issue future guidance on the transition. The transition will undoubtedly have many complexities, and there will be challenges for some use cases such as IoT devices or certificate transparency.
References
Alagic G., Alperin-Sheriff J., et al. (2019) Status report on the first round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8240. – Режим доступу: https://doi.org/10.6028/NIST.IR.8240.
Alagic G., Alperin-Sheriff J., et al. (2020) Status report on the second round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8309. Режим доступу: https://doi.org/10.6028/NIST.IR.8309.
NIST PQC. [Електронний ресурс]. Режим доступу: https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization.
Schank J. (2021) Category 5 NTRU parameters. [Електронний ресурс]. Режим доступу: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/t1JCgzSS-uk/m/VXXQaJgFCQAJ.
National Institute of Standards and Technology (2016) Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Режим доступу: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.
Bernstein D., Lange T. (eds.), eBACS: ECRYPT Benchmarking of Cryptographic Systems – SUPERCOP (2020). [Електронний ресурс]. Режим доступу: https://bench.cr.yp.to/supercop.html.
Shulman H., Goodman J., et al. (2021) PANEL: PQC considerations for DNSSEC, Third PQC Standardization Conference. [Електронний ресурс]. Режим доступу: https://www.nist.gov/video/third-pqc-standardization-conference-session-v-applications.
Bindel N. (2021) Suitability of 3rd round signature candidates for vehicle-to-vehicle communication // Workshop Record of the Third PQC Standardization Conference. [Електронний ресурс]. Режим доступу: https://csrc.nist.gov/Presentations/2021/suitability-of-3rd-round-signature-candidates-for.
Berlekamp E., McEliece R,, van Tilborg H. (1978) On the inherent intractability of certain coding problems (corresp.) // IEEE Transactions on Information Theory 24(3): 384-386. Режим доступу: https://doi.org/10.1109/TIT.1978.1055873.
Prange E. (1962) The use of information sets in decoding cyclic codes // IRE Transactions on Information Theory 8(5): 5-9. Режим доступу: https://doi.org/10.1109/TIT.1962.1057777.
Bernstein D. J. (2010) Grovervs. McEliece. Post-Quantum Cryptography, ed Kachigar G., Tillich J. P. (2017) Quantum information set decoding algorithms. Post-Quantum Cryptography, eds Lange T., Takagi T. (Springer International Publishing, Cham), pp. 69-89.
Kachigar G., Tillich J. P. (2017) Quantum information set decoding algorithms. Post-Quantum Cryptography, eds Lange T., Takagi T. (Springer International Publishing, Cham), pp. 69-89.
Kirshanova E. (2018) Improved quantum information set decoding. Post-Quantum Cryptography, eds Lange T., Steinwandt R. (Springer International Publishing, Cham), pp. 507-527.
Esser A., Ramos-Calderer S., et al. (2021) An optimized quantum implementation of ISD on scalable quantum resources, Cryptology ePrint Archive, Report 2021/1608. Режим доступу: https://ia.cr/2021/1608.
Patarin J., Goubin L. (1997) Trapdoor one-way permutations and multivariate polynominals // Proceedings of the First International Conference on Information and Communication Security ICICS’97 (Springer-Verlag, Berlin, Heidelberg), p. 356-368.
Buss J. F., Frandsen G. S., Shallit J. O. (1996) The computational complexity of some problems of linear algebra. BRICS Report Series 3(33). Режим доступу: https://doi.org/10.7146/brics.v3i33.20013.
Faugere J. C. (1999) A new efficient algorithm for computing Grobner bases (F4). Journal of Pure and Applied Algebra 139(1): 61-88. Режим доступу: https://doi.org/https://doi.org/10.1016/S0022-4049(99)00005-5.
Faugere J. C. (2002) A new efficient algorithm for computing Grobner bases without reduction to zero (F5) // Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation ISSAC’02 (Association for Computing Machinery, New York, NY, USA), p. 75-83. Режим доступу: https://doi.org/10.1145/780506.780516.
Courtois N., Klimov A., Patarin J,, Shamir A. (2000) Efficient algorithms for solving overdefined systems of multivariate polynomial equations. Advances in Cryptology – EUROCRYPT 2000, ed Preneel B. (Springer Berlin Heidelberg, Berlin, Heidel- berg), pp. 392-407.
Goubin L., Courtois N. T. (2000) Cryptanalysis of the TTM cryptosystem. Advances in Cryptology – ASIACRYPT 2000, ed Okamoto T. (Springer Berlin Heidelberg, Berlin, Heidelberg), pp. 44-57.
Bardet M., Bros M., et al. (2020) Improvements of algebraic attacks for solving the rank decoding and MinRank problems. Advances in Cryptology – ASIACRYPT 2020, eds Moriai S., Wang H. (Springer International Publishing, Cham), pp. 507-536.
Ajtai M. (1996) Generating hard instances of lattice problems (extended abstract). Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing STOC’96 (Association for Computing Machinery, New York, NY, USA), p. 99-108. Режим доступу: https://doi.org/10.1145/237814.237838.
Katz J., Lindell Y. (2020) Introduction to Modern Cryptography (Chapman & Hall/CRC), 3rd Ed.
Tao C., Petzoldt A., Ding J. (2020) Improved key recovery of the HFEv- signature scheme // Cryptology ePrint Archive, Report 2020/1424. Режим доступу: https://ia.cr/2020/1424.
Beullens W. (2021) Improved cryptanalysis of UOV and Rainbow. Advances in Cryptology – EUROCRYPT 2021, eds Canteaut A., Standaert F. X. (Springer International Publishing, Cham), pp. 348-373.
Beullens W. (2022) Breaking Rainbow takes a weekend on a laptop, Cryptology ePrint Archive, Report 2022/214. Режим доступу: https://ia.cr/2022/214.
pqm4: Post-quantum crypto library for the ARM Cortex-M4 (2020). [Електронний ресурс]. Режим доступу: https://github.com/mupq/pqm4.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
