Multivariate Cryptography Comes Storming Back for PQC

Prof Bill Buchanan OBE FRSE
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…

--

--

Prof Bill Buchanan OBE FRSE

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