Rainbow — The PCQ Oil and Vinegar Method: Small Signatures, But Larger Keys (than Lattice)
Here’s my 6 am doodles from this morning on multivariate cryptography:
Our existing methods of public-key encryption — such as discrete logs, RSA and elliptic curve — are known not to be a hard problem in a world of quantum computers. Multivariate cryptography is a known hard problem and is robust against quantum computers. Examples of methods that use multivariate cryptography are Oil-and-Vinegar, Unbalanced Oil and Vinegar, and Rainbow. While the original Oil-and-Vinger method has been cracked, we have advanced to Rainbow, and which is one of the finalists for the final round of the NIST competition for PQC (Post-Quantum Cryptography) signatures:
Multivariate cryptography
With multivariate cryptography, we have n variables within polynomial equations. For example, if we have four variables (w, x, y, z) and an order of two, we could have [here]:
