Generation of general system parameters for Rainbow electronic signature scheme for 384 and 512 security bits
DOI:
https://doi.org/10.30837/rt.2021.1.204.02Keywords:
attacks, multivariate transformations, electronic signature, general system parameters, RainbowAbstract
Today, there is rapid progress in the creation of quantum computers to solve various computational problems and for different purposes. At the same time, special efforts are made to create such a quantum computer that can solve the problems of cryptanalysis of existing cryptosystems: asymmetric ciphers, key encapsulation protocols, electronic signatures, etc. Prevention of such threats can be achieved by developing cryptographic systems that will be protected against both quantum and classical attacks, and be able to interact with existing protocols and communication networks. There is also a significant need for protection against attacks by side channels. Currently, significant efforts of cryptologists are focused on the NIST PQC open competition. The main idea of the NIST PQC competition is to define mathematical methods based on which standards for asymmetric cryptotransformations, primarily electronic signatures, as well as asymmetric ciphers and key encapsulation protocols can be developed. Three electronic signature schemes – Crystals-Dilithium, Falcon and Rainbow become the finalists of the third stage of the NIST PQC competition according to the results of the second stage. The first two are based on the mathematics of algebraic lattices, and Rainbow is based on multivariate transformations. Currently, a comprehensive analysis of the finalists is an important task for the entire global crypto community. The vast majority of schemes that have become finalists or alternative algorithms are based on problems in the theory of algebraic lattices. Special attention was also paid to the Rainbow electronic signature scheme based on multivariate transformations. The purpose of this work consists in a preliminary analysis of existing attacks on promising electronic signature Rainbow, definition of requirements to the system-wide parameters to ensure cryptographic stability of at least 512 bits against classical and 256 bits against quantum cryptanalysis, as well as development and practical implementation of Rainbow algorithms for generating system-wide parameters for 512 bits against classical and 256 bits against quantum cryptanalysis.
References
PQC Standardization Process: Third Round Candidate Announcement. July 22, 2020. [Electronic resource]. Access mode: https://csrc.nist.gov/News/2020/pqc-third-round-candidate-announcement.
Craig Gentry, Chris Peikert, Vinod Vaikuntanathan Trapdoors for hard lattices and new cryptographic constructions // Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 197–206. ACM Press, May 2008.
Damien Stehlé, Ron Steinfeld Making NTRU as secure as worst-case problems over ideal lattices // Kenneth G. Paterson, editor, EUROCRYPT 2011, volume 6632 of LNCS, pages 27–47, Tallinn, Estonia, May 15–19, 2011. Springer, Heidelberg, Germany.
Thomas Prest Gaussian Sampling in Lattice-Based Cryptography. Theses, École Normale Supérieure, December 2015.
A. Kipnis, J. Patarin, L. Goubin Unbalanced Oil and Vinegar schemes // EUROCRYPT 1999, LNCS vol. 1592, pp. 206-222. Springer, 1999.
Rainbow Signature / Ding J. and other.2020. P. 16-22. Access mode: https://www.pqcrainbow.org/.
J. Ding, D. Schmidt Rainbow, a new multivariable polynomial signature scheme // ACNS 2005, LNCS vol. 3531, pp. 164-175. Springer, 2005.
J. Bonneau, I. Mironov Cache-Collision Timing Attacks Against AES. CHES 2006, LNCS vol. 4249, pp. 201-215. Springer, 2006.
Magali Bardet, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Ray A. Perlner, Daniel Smith-Tone, Jean-Pierre Tillich, Javier A. Verbel Algebraic attacks for solving the Rank Decoding and MinRank problems without Groebner basis. CoRR abs/2002.08322 (2020).
D. Coppersmith, J. Stern, S. Vaudenay Attacks on the birational signature scheme. CRYPTO 1994, LNCS vol. 773, pp. 435-443. Springer, 1994.
A. Kipnis, A. Shamir Cryptanalysis of the Oil and Vinegar signature scheme. CRYPTO 1998, LNCS vol. 1462, pp. 257-266. Springer, 1998.
J. Ding, B.-Y. Yang, C.-H. O. Chen, M.-S. Che, C.-M. Cheng: New differential-algebraic attacks and reparametrization of Rainbow // ACNS 2008, LNCS vol. 5037, pp. 242-257. Springer, 2008.
J. Ding, Z. Zhang, J. Deaton, K. Schmidt, F. Visakha New attacks on lifted unbalanced oil vinegar. The 2nd NIST PQC Standardization Conference, 2019.
A. Kipnis, A. Shamir Cryptanalysis of the Oil and Vinegar signature scheme. CRYPTO 1998, LNCS vol. 1462, pp. 257-266. Springer, 1998.
A. Petzoldt, S. Bulygin, J. Buchmann Cyclic Rainbow – a Multivariate Signature Scheme with a Partially Cyclic Public Key. INDOCRYPT 2010, LNCS vol. 6498, pp. 33 – 48. Springer, 2010.
A. Petzoldt: Efficient Key Generation for the Rainbow Signature Scheme. PQCrypto 2020.
E. Thomae C. Wolf: Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited. PKC 2012, LNCS vol. 7293, pp. 156-171. Springer, 2012.
W. Beullens, B. Preneel, A. Szepieniec, F. Vercauteren LUOV signature scheme proposal for NIST PQC project (Round 2 version), 2019.
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).
