One of the Three NIST Post-quantum Signature Finalists
Rainbow belongs to the family of the multivariate public key cryptosystems, one of the main families of post-quantum cryptosystems. Rainbow was designed in 2004 by Jintai Ding and Dieter Schmidt and it is based on the Oil-Vinegar signature scheme invented by Jacques Patarin. In July 22. 2020, Rainbow was select as one of the three NIST Post-quantum signature finalists.
The theoretical security of Rainbow is based on the fact that solving a set of random multivariate quadratic system is an NP-hard problem. The mathematical theory behind is the theory of multivariate polynomials -- algebraic geometry.
Rainbow offers very small signatures of only a few hundred bits (only 528 bits=66 bytes for the NIST level I security), which are much shorter than those of other (post-quantum) signature schemes. Furthermore, since Rainbow uses only simple operations over small finite fields, signature generation and verification are extremely efficient.
A Toy Program in Magma
Here is a Magma program for someone who wants to play with Rainbow.
In the calculator, one has to copy and paste the program into the window of the calculator and then press the submit button.
You can change anything in the program, in particular, the parameters for Rainbow at the beginning of the code which can be modified as you want. The three number in parameters vector are v_1, o_1 and o_2, which is set to be [ 3, 2, 2] for now.
The program will generate the public and private keys, it will then create a random hashvalue, which will be signed. The signature is then verified in the last part of the program with the help of the public key.
Normally this program would be implemented in three separate programs with the keys passed on in external files. The magma calculator does not allow for external files, therefore everything is done immediately in sequence.