Generation of general system parameters for Rainbow signature scheme

Fìz.-mat. model. ìnf. tehnol. 2021, 33:83-87

Abstract

The paper considers the description of electronic signature scheme Rainbow, which is based on multivariate transformations. It is a generalization of the UOV structure, which provides efficient parameterization due to the additional algebraic structure. The article provides an initial analysis of known attacks on the ES Rainbow scheme. Also, algorithms for generating general system parameters for 384 and 512 security bits were developed and the results are presented in this paper. The study found that the Rainbow signature generation process consists of simple operations of linear algebra, such as multiplying matrix vectors and solving linear systems over small finite fields. Another advantage of Rainbow is that this scheme offers very small signatures of only a few hundred bits. But the main disadvantage of Rainbow is the large size of public keys.

References

1. PQC Standardization Process: Third Round Candidate Announcement. https://csrc.nist.gov/News/2020/pqc-third-round-candidate-announcement
2. Kipnis, A., Patarin, J., Goubin, L. (1999). Unbalanced Oil and Vinegar schemes. EUROCRYPT, LNCS, Springer, 1592, 206-222.
   DOI https://doi.org/10.1007/3-540-48910-x_15
3. Ding J. (2020). Rainbow Signature.
4. Bardet, M. (2020). Algebraic attacks for solving the Rank Decoding and MinRank problems without Groebner basis.
5. Coppersmith, D., Stern, J., Vaudenay, S. (1994). Attacks on the birational signature scheme. CRYPTO 1994, LNCS, Springer, 773, 435-443.
   DOI https://doi.org/10.1007/3-540-48329-2_37
6. Kipnis, A., Shamir, A. (1998). Cryptanalysis of the Oil and Vinegar signature scheme. CRYPTO 1998, LNCS, Springer, 1462, 257-266.
   DOI https://doi.org/10.1007/bfb0055733
7. Ding, J. (2008). New differential-algebraic attacks and reparametrization of Rainbow. ACNS 2008, LNCS, Springer, 5037, 242-257.