# Multivariate Cryptography Comes Storming Back for PQC

--

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**. These are the latest methods that are proposed for the standardization of PQC (Post-Quantum Cryptography) signatures with Multivariate methods [here]:

## 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]:

*w*²+4*wx*+3*x*²+2*wy*−4*wz*+2*wx*+6*xz*=387

In this case, I know that the solution is w=7, x=4, y=5, z=6. For a matrix form, we could represent this as:

In order to constrain the values we get, we normally perform a (mod *p*) operation and where *p* is a prime number. This is known as a finite field, and our numbers are always constrained between 0 and p-1. For example, if we select *p*=97, we have:

*w*²+4*wx*+3*x*²+2*wy*−4*wz*+2*wx*+6*xz*=5 (mod 97)

Now there are multiple solutions to this now for *w*, *x*, *y *and *z*, so we define *n *multivariate polynomials. For example:

*w*²+4*wx*+3*x*²+2*wy*−4*wz*+2*wx*+6*wx*=96 (mod 97)

*5w²*+3*wx*+3*x²*+4*wy*−*wz*+8*wx*+4*wx*=36 (mod 97)

*4w*²+5*wx*+3*x²*+2*wy*−5*wz*+3*wx*+6*wx*=95 (mod 97)

*6w*2+7*wx*+4*x*2+2*wy*−8*wz*+2*wx*+9*wx*=17 (mod 97)