Analysis of security of post-quantum algorithm of Rainbow electronic signature against potential attacks
Keywords:multidimensional cryptography, attack analysis, postquantum period
Multidimensional public key cryptography is a candidate for post-quantum cryptography, and it makes it possible to generate particularly short signatures and quick verification. The Rainbow signature scheme proposed by J. Dean and D. Schmidt is such a multidimensional cryptosystem and it is considered to be protected against all known attacks. The need for research on Rainbow ES is justified by the fact that there is a need to develop and adopt a post-quantum national securities standard, and that in the process of the US NIST competition on the mathematical basis of cryptographic transformation method Rainbow, promising results. Therefore, it is considered important to take them into account and use them in Ukraine. The Rainbow signature scheme can be implemented simply and efficiently using linear algebra methods over a small finite field and, in particular, creates shorter signatures than those used in RSA and other post-quantum signatures . In the 2nd round of NIST PQC, protected sets of Rainbow parameters are offered and several attacks on them are analyzed . When comparing ES, preference is given to ES algorithms that have been selected according to unconditional criteria, as well as those that have better indicators for integral conditional criteria, because such a technique is more rational. In particular, the Rainbow-Band-Separation (RBS) attack  is the best known Rainbow attack with a certain set of parameters and is important. The Rainbow-Band-Separation attack restores the Rainbow secret key by solving certain systems of quadratic equations, and its complexity is measured by a well-known measure called the degree of regularity. However, as a rule, the degree of regularity is greater than the degree of solution in experiments, and it is impossible to obtain an accurate estimate. The paper proposes a new indicator of the complexity of the Rainbow-Band-Separation attack using F4 algorithm, which gives a more accurate estimate compared to the indicator that uses the degree of regularity.
The aim of the work is a comparative analysis of ES based on MQ-transformations on the criterion of stability-complexity and an attempt to understand the security of Rainbow against RBS attack using F4.
Ding J., Chen M.-S., Petzoldt A., Schmidt D., Yang B. Y. Rainbow – Algorithm Specification and Documentation. Specification document of NIST PQC 2nd round submission package (2019)
Ding J., Yang B.-Y., Chen C.-H. O., Chen M.-S. and Cheng C.-M. New differential-algebraic attacks and reparametrization of Rainbow // Bellovin, S.M., Gennaro, R., Keromytis, A.D., Yung, M. (eds.) ACNS 2008, LNCS, vol. 5037, pp. 242–257. Springer (2008).
Кудряшов І. С., Малєєва Г. А. Аналіз властивостей електронних підписів на базі MQ перетворень / Ін-т кібернетики імені В. М. Глушакова НАН України ; Кам’янець-Подільський нац. ун-т імені Івана Огієнка // Математичне та комп’ютерне моделювання / Кам’янець-Подільський нац. ун-т імені Івана Огієнка. Кам’янець-Подільський, 2019. (Технічні науки: зб. наук праць; 19). С. 69-74.
Thomae E. A Generalization of the Rainbow Band Separation Attack and its Applications to Multivariate Schemes // IACR Cryptology ePrint Archive (2012). https://eprint.iacr.org/2012/223.
Nakamura S., Ikematsu Y., Wang Y., Ding J., Takagi Т. New Complexity Estimation on the Rainbow-Band-Separation Attack. Specification document of NIST PQC.
Coppersmith D., Stern J., Vaudenay S. Attacks on the birational signature scheme // Stinson D.R. (ed.) CRYPTO 1994, LNCS vol. 773, pp. 435–443. Springer (1994).
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).