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²+4wx+3x²+2wy−4wz+2wx+6xz=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²+4wx+3x²+2wy−4wz+2wx+6xz=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²+4wx+3x²+2wy−4wz+2wx+6wx=96 (mod 97)
5w²+3wx+3x²+4wy−wz+8wx+4wx=36 (mod 97)
4w²+5wx+3x²+2wy−5wz+3wx+6wx=95 (mod 97)
6w2+7wx+4x2+2wy−8wz+2wx+9wx=17 (mod 97)
