Analysis of the RAINBOW post-quantum electronic signature algorithm state and attacks on it for the period of the NIST PQC third round completion
Keywords:electronic signature, cryptographic stability, cryptanalysis, quantum cryptanalysis
The paper identifies and analyzes attacks aimed at cryptanalysis of the Rainbow post-quantum electronic signature algorithm and the state of this electronic signature within the framework of the NIST PQC competition and as a whole. The Rainbow electronic signature as a candidate in the third round of the NIST PQC was examined in detail for the possibility of cryptanalysis. The possibility to use this quantitative attack on the Rainbow electronic signature and the complexity of such an attack depends on the possibility to use this electronic signature in the post-quantum period. Also during the NIST PQC report on the peculiarities of the adoption of the first post-quantum standards, which took place on March 8-11, 2022, some concerns about the Rainbow's security were mentioned due to the implementation of an attack on one of the parameter sets (although the parameter set of the second round). Some details of this attack were discussed in the paper to understand better the state of the Rainbow's electronic signature at the end of the third round of the NIST PQC.
Post-Quantum Cryptography PQC. Round 3 Submissions. NIST Computer Security Resource Center (CSRC). URL: https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions (last accessed on 16.06.2022).
PQC Standardization Process: Third Round Candidate Announcement. NIST Computer Security Resource Center (CSRC). July 22, 2020. URL: https://csrc.nist.gov/News/2020/pqc-third-round-candidate-announcement (last accessed on 15.06.2022).
Jintai Ding. Rainbow – Algorithm Specification and Documentation. The 3d round Proposal. Department of Mathematical Sciences, University of Cincinnati.
J.-C. Faugere. A new efficient algorithm for computing Grobner Bases (F4). Journal of Pure and Applied Algebra, 139 (1999) 61-88. DOI: https://doi.org/10.1016/S0022-4049(99)00005-5 (last accessed on 13.06.2022).
L. Bettale, J.-C. Faugere, L. Perret. Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology, 3, pp. 177-197, 2009.
D. Coppersmith, J. Stern, S. Vaudenay. Attacks on the birational signature scheme. CRYPTO 1994, pp. 435-443. Springer, 1994.
A. Kipnis, J. Patarin, L. Goubin. Unbalanced Oil and Vinegar schemes. EUROCRYPT 1999, pp. 206-222. Springer, 1999.
A. Kipnis, A. Shamir. Cryptanalysis of the Oil and Vinegar signature scheme. CRYPTO 1998, pp. 257-266. Springer,1998.
P. Schwable, B. Westerbaan. Solving Binary MQ with Grover’s Algorithm. SPACE 2016, pp. 303-322. Springer 2016.
Post-Quantum Cryptography PQC. The Beginning of the End: The First NIST PQC Standards. NIST Computer Security Resource Center (CSRC). URL: https://csrc.nist.gov/Presentations/2022/the-beginning-of-the-end-the-first-nist-pqc-standa (last accessed on 13.06.2022).
W. Beullens. Breaking Rainbow Takes a weekend on a Laptop. Cryptology ePrint Archive 2022/214. URL: https://eprint.iacr.org/2022/214 (last accessed on 17.06.2022).
How to Cite
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).