Quantum attack against post-quantum electronic signature complexity and implementation probability analysis

Fìz.-mat. model. ìnf. tehnol. 2021, 32:136-140

Abstract

The paper identifies and analyzes attacks aimed at Rainbow post-quantum electronic signature cryptanalysis. Today, due to advances in the quantum computers development, the need to present new standards for electronic signatures resistant to both quantum and classical cryptanalysis arisen. To solve the lack of such electronic signatures, NIST USA is running the NIST PQC competition. As part of this competition some electronic signatures designed to resist quantum cryptanalysis were presented, including Rainbow electronic signature. CZ-Rainbow and the compressed Rainbow algorithm were also presented along with the regular Rainbow algorithm. This paper analysis attacks on all three types of electronic signature. The possibility of a quantum attack against the Rainbow electronic signature, as well as the complexity of such an attack, defines the possibility of this electronic signature usage during the post-quantum period.

References

1. Post-Quantum Cryptography PQC. Round 3 Submissions. NIST Computer Security Resource Center (CSRC). Information retrieval interaction. Retrieved from https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.
2. PQC Standardization Process: Third Round Candidate Announcement. NIST Computer Security Resource Center (CSRC). July 22, 2020. Information retrieval interaction. Retrieved from https://csrc.nist.gov/News/2020/pqc-third-round-candidate-announcement.
3. Ding, J. Rainbow - Algorithm Specification and Documentation. The 3rd round Proposal. Department of Mathematical Sciences, University of Cincinnati.
4. Faugere, J.-C. (1999). A new efficient algorithm for computing Grobner Bases (F4). Journal of Pure and Applied Algebra, 139, 61-88. Information retrieval interaction. Retrieved from https://doi.org/10.1016/S0022-4049(99)00005-5.
   DOI doi.org/10.1016/s0022-4049(99)00005-5
5. Bettale, L., Faugere, J.-C., Perret, L. (2009). Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology, 3, 177-197, 2009.
   DOI doi.org/10.1515/jmc.2009.009
6. Coppersmith, D., Stern, J., Vaudenay, S. (1994). Attacks on the birational signature scheme. CRYPTO 1994. Springer, 435 – 443.
   DOI doi.org/10.1007/3-540-48329-2_37
7. Kipnis, A., Patarin, J., Goubin, L. (1999). Unbalanced Oil and Vinegar schemes. EUROCRYPT 1999. Springer, 206-222.
   DOI doi.org/10.1007/3-540-48910-x_15
8. Kipnis, A., Shamir, A. (1998). Cryptanalysis of the Oil and Vinegar signature scheme. CRYPTO 1998. Springer, 257-266.
   DOI doi.org/10.1007/bfb0055733
9. Schwable, P., Westerbaan, B. (2016). Solving Binary MQ with Grover’s Algorithm. Springer. SPACE 2016, 303-322.