Multivariate Cryptography Comes Storming Back for PQC

Prof Bill Buchanan OBE
5 min readSep 20, 2023

--

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+3+4wywz+8wx+4wx=36 (mod 97)

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

6w2+7wx+4x2+2wy−8wz+2wx+9wx=17 (mod 97)

--

--

Prof Bill Buchanan OBE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.