Analysis of security of post-quantum algorithm of Rainbow electronic signature against potential attacks


  • G.А. Maleeva



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 [1]. In the 2nd round of NIST PQC, protected sets of Rainbow parameters are offered and several attacks on them are analyzed [1]. 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 [2] 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).

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

Maleeva , G. . (2021). Analysis of security of post-quantum algorithm of Rainbow electronic signature against potential attacks. Radiotekhnika, 2(205), 85–93.