Finally, Multivariate Cryptography Should Take Centre Stage

In cryptography, we like finite fields. Why? Because they constrain our outputs and make our computations much simpler than having an infinite field. So, many of our calculations in public key encryption involve the (mod p) operation, which still allows us to use our normal arithmetic operators but contains within a finite field of zero to p-1.

With multivariate cryptography (MC), we use multivariate polynomials within a finite field of p. Overall, solving these polynomials has been proven to be NP-complete and is thus suited for post-quantum robustness for digital signatures, especially because they have a short signature value. Examples of methods that use multivariate cryptography are oil-and-vinegar, unbalanced oil and vinegar (UOV), and rainbow. Overall, Rainbow was one of the finalists for the final round of the NIST competition for PQC (Post-Quantum Cryptography) signatures. In Round 1, Additional Signatures, NIST is evaluating a number of new methods, which are typically based on the UOV approach.

Multivariate cryptography (MC)

For MC, 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]: