Rainbow Signature
One of the Three NIST Post-quantum Signature Finalists
About Rainbow
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.
There are a short and a long videos about MPKCs and Rainbow you can watch. The NIST second round presentation is also a good place to learn the basics about Rainbow.
The Rainbow Team
The Rainbow team consists of (in alphabetical order):
NIST Submission
Third Round Rainbow Parameter Update
The third round submission documents of Rainbow will be uploaded soon after it is submitted to NIST.
This is the link to the second round submission documents for Rainbow.
Softwares
The new software for the updated parameters is available here.
A Toy Program in Magma
Here is a Magma program for someone who wants to play with Rainbow.
This file is a toy Magma Rainbow program, which can run on Magma or the online magma calculator
http://magma.maths.usyd.edu.au/calc/
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.