Chapter 24Multivariate Cryptography
24.1Learning objectives#
The book has now surveyed lattices, hash functions, and codes. This chapter opens a fourth, again independent, hard-problem family. Multivariate cryptography abandons vectors, hashes, and codewords for a very different object: a system of nonlinear equations. Its security rests on a fact that predates cryptography itself – solving a system of multivariate quadratic equations over a finite field is, in general, computationally intractable, and no quantum algorithm is known to change that. The idea is old (it dates to the late 1980s and 1990s [1]) and it has a turbulent history: many concrete proposals have been broken, sometimes years after they were thought safe. That history is worth studying in its own right, because it teaches, more sharply than any other family, how a structured trapdoor can be reverse-engineered.
After finishing this chapter, you should be able to:
state the multivariate quadratic (MQ) problem – solving a system of quadratic equations over \(\mathbb{F}_q\) – and explain why its NP-hardness (with no known quantum shortcut beyond Grover) is the security foundation of the family;
work through a tiny quadratic system over a small field and see why brute force costs \(q^n\);
describe the shared trapdoor idea: a public system \(P = S \circ F \circ T\) that looks random, built from an easily invertible central map \(F\) hidden between two secret linear maps \(S\) and \(T\);
explain why multivariate schemes are almost always signatures – tiny signatures, very large public keys – rather than KEMs;
describe the oil-and-vinegar construction and its unbalanced variant UOV, understand why the layered variant Rainbow was a NIST finalist, and know that Rainbow was broken in 2022;
place multivariate cryptography as one of the five post-quantum families, and state honestly that – unlike the lattice and hash families – it has no FIPS standard as of this writing.
Why this chapter matters.#
Post-quantum security is a portfolio of independent bets, and multivariate cryptography is one of its more distinctive holdings. Where the lattice and code families deliver both encryption and signatures, the multivariate family is almost entirely a signature technology, and a specialized one: its signatures are among the smallest of any post-quantum scheme, at the cost of public keys measured in kilobytes to megabytes. It is also the family whose flagship candidates have been broken most publicly, which makes it a case study in the central tension of trapdoor design – the very structure that lets the legitimate signer invert the system is the structure an attacker tries to detect. Understanding both the promise and the fragility rounds out the picture of what post-quantum cryptography is [2].
24.2The hard problem: multivariate quadratics#
Every scheme in this chapter reduces, for the attacker, to the same underlying task: given a system of quadratic equations, find a common solution.
Definition 24.1 (Multivariate quadratic (MQ) problem). Let \(\mathbb{F}_q\) be a finite field. Given \(m\) quadratic polynomials \(p_1,\dots,p_m \in \mathbb{F}_q[x_1,\dots,x_n]\) and a target vector \(y = (y_1,\dots,y_m) \in \mathbb{F}_q^m\), find, if it exists, a vector \(x = (x_1,\dots,x_n) \in \mathbb{F}_q^n\) such that \[p_k(x) = y_k \qquad \text{for all } k = 1,\dots,m .\] Each polynomial has the form \[p_k(x) = \sum_{1 \le i \le j \le n} a^{(k)}_{ij}\, x_i x_j \;+\; \sum_{i=1}^{n} b^{(k)}_i\, x_i \;+\; c^{(k)} ,\] with all coefficients in \(\mathbb{F}_q\).
A single quadratic equation is easy; a large system of them, sharing variables, is not. Deciding whether such a system has a solution is NP-complete, and this holds even over the smallest field \(\mathbb{F}_2\) [1]. The intuition is that the quadratic terms couple the variables together so tightly that fixing some of them does not straightforwardly simplify the rest, and there is no linear-algebra shortcut analogous to Gaussian elimination.
The best classical attacks compute a Gröbner basis of the system (via algorithms such as \(F_4\)/\(F_5\)) or run the closely related XL linearization; both run, on random-looking instances, in time exponential in \(n\) once \(m\) and \(n\) are comparable. Quantum computers do not overturn this. As with every family in this part of the book, the strongest quantum approach applies Grover-style search and buys at most a square-root speedup, the same mild erosion described in the Quantum Threat chapter. There is no Shor-like collapse: MQ has no known efficient quantum algorithm, and doubling the parameters restores any margin a quantum search would erode.
Example 24.2 (A tiny system over \(\mathbb{F}_2\)). Take \(\mathbb{F}_2 = \{0,1\}\), where addition is XOR and multiplication is AND, and note that \(x_i^2 = x_i\) there, so the only genuine quadratic monomials are the products \(x_i x_j\) with \(i \neq j\). Consider two quadratic polynomials in three variables, \[p_1(x) = x_1 x_2 + x_1 x_3 + x_2 , \qquad p_2(x) = x_2 x_3 + x_1 + x_3 ,\] and the target \(y = (1,0)\). We seek \(x \in \mathbb{F}_2^3\) with \(p_1(x) = 1\) and \(p_2(x) = 0\). With only \(2^3 = 8\) candidates we can simply enumerate; doing so reveals three solutions, among them \(x = (0,1,0)\): \[p_1(0,1,0) = 0 + 0 + 1 = 1 , \qquad p_2(0,1,0) = 0 + 0 + 0 = 0 .\] Brute force worked here only because the field and the dimension are tiny. In general an attacker faces \(q^n\) candidate vectors, and a real scheme chooses \(q\) and \(n\) so that \(q^n\) – and, more precisely, the cost of the Gröbner/XL attacks, which is far below \(q^n\) but still exponential – is astronomically large.
This is the security foundation. If we can hand an attacker a system of quadratics that looks random, then forging without the trapdoor means solving an MQ instance.
24.3The trapdoor: a solvable system in disguise#
The difficulty is the familiar one: if the public system were genuinely random, then nobody – not even the legitimate key holder – could solve it, and there would be no way to sign. Multivariate cryptography resolves this exactly as code-based cryptography does, by hiding an easy problem inside a hard-looking one.
The central map.#
The secret starts with a central map \(F = (f_1,\dots,f_m) : \mathbb{F}_q^n \to \mathbb{F}_q^m\), a system of quadratics chosen with special structure so that it can be inverted efficiently: given a target \(a \in \mathbb{F}_q^m\), the key holder can quickly find some \(b\) with \(F(b) = a\). The particular structure that makes \(F\) invertible is the design choice that distinguishes one multivariate scheme from another; the oil-and-vinegar structure of the next section is the most durable example.
The disguise.#
Left in the open, the structure of \(F\) would be plainly visible and an attacker could invert it too. So it is hidden between two secret invertible affine (for our purposes, linear) maps: an \(n \times n\) map \(T\) applied to the input, and an \(m \times m\) map \(S\) applied to the output. The public key is the composition \[P = S \circ F \circ T ,\] expanded out and published as \(m\) explicit quadratic polynomials in \(n\) variables. Composing with the linear maps \(S\) and \(T\) keeps \(P\) quadratic, but it stirs the coefficients so thoroughly that the special shape of \(F\) disappears: to anyone without \(S\), \(F\), and \(T\), the public system \(P\) looks like a random system of quadratics, and solving it looks like MQ.
Signing, not encrypting.#
Notice which direction is easy. Evaluating \(P\) at a point is cheap and needs no secret – it is just plugging numbers into polynomials. Inverting \(P\), finding an \(x\) with \(P(x) = y\), is hard without the trapdoor. This asymmetry is exactly backwards from an encryption scheme, where anyone must be able to encrypt (compute the forward direction) and only the key holder decrypts. It fits a signature scheme perfectly: to sign a message \(M\), hash it to a target \(y = \mathcal{H}(M) \in \mathbb{F}_q^m\) and use the trapdoor to invert, producing a signature \(x\) with \(P(x) = y\); to verify, anyone evaluates \(P(x)\) and checks that it equals \(\mathcal{H}(M)\). For this reason multivariate schemes are almost always signatures. Encryption variants exist but have fared poorly, and the signatures are where the family’s strengths – very small signatures and fast verification – actually appear.
24.4Oil and vinegar#
The oldest central-map structure still standing is oil and vinegar, introduced by Patarin and analysed in its unbalanced form by Kipnis, Patarin, and Goubin in 1999 [3]. Its inversion trick is a small marvel of linear algebra.
Definition 24.3 (Oil-and-vinegar central map). Partition the \(n\) variables into \(v\) vinegar variables \(x_1,\dots,x_v\) and \(o\) oil variables \(x_{v+1},\dots,x_{v+o}\), with \(n = v + o\). A quadratic polynomial \(f_k\) is of oil-and-vinegar type if every quadratic term contains at least one vinegar variable – equivalently, no two oil variables are ever multiplied together: \[f_k(x) = \sum_{i=1}^{v}\sum_{j=1}^{n} \alpha^{(k)}_{ij}\, x_i x_j \;+\; \sum_{i=1}^{n} \beta^{(k)}_i\, x_i \;+\; \gamma^{(k)} .\] The central map is \(F = (f_1,\dots,f_o)\), with one polynomial per oil variable.
The oil variables are so named because, like oil in water, they never mix with one another – only ever with vinegar. That single restriction is what makes \(F\) invertible.
Proposition 24.4 (Inversion by linearization). Fix the vinegar variables to arbitrary field elements \(x_1 = r_1,\dots,x_v = r_v\). Then each \(f_k\), viewed as a function of the remaining oil variables alone, is linear: every surviving quadratic term had a vinegar factor, which is now a constant. Solving \(F = a\) therefore reduces to a system of \(o\) linear equations in the \(o\) oil unknowns, which is solved by Gaussian elimination.
So to invert \(F\) on a target \(a\): pick random values for the vinegar variables, substitute them, and solve the resulting linear system for the oil variables. If the linear system happens to be singular, re-randomize the vinegar values and try again. This is fast, and it is exactly the trapdoor step \(F^{-1}\) used in signing.
Remark 1.1. In pure single-layer UOV the outer map \(S\) can be omitted (a single layer’s output can be re-mixed into the central map without weakening it), so many descriptions write the public key as \(P = F \circ T\). We keep \(S\) explicit to match the general \(P = S \circ F \circ T\) template, which is the right picture for the layered schemes below.
Balanced versus unbalanced.#
Patarin’s original proposal took \(v = o\). Kipnis and Shamir broke that balanced version, and the fix, due to Kipnis, Patarin, and Goubin, was to make the scheme unbalanced – take many more vinegar variables than oil, \(v \gg o\) [3]. This is Unbalanced Oil and Vinegar (UOV). The extra vinegar variables enlarge the hidden subspace an attacker must find and defeat the balanced attack. UOV, with conservative parameters, has resisted attack for over two decades and is the stable core of the whole family.
Rainbow: layers, and a fall.#
Rainbow stacks several oil-and-vinegar maps in layers, each layer’s variables serving as vinegar for the next. Layering shrinks the keys and signatures relative to plain UOV, and on that strength Rainbow advanced to the third round of the NIST post-quantum project as one of three signature finalists. Then, in 2022, Beullens found a key-recovery attack that exploited the extra algebraic structure the layers introduced, recovering a Rainbow private key at the claimed lowest security level in about a weekend on a single laptop [4]. The break did not touch the MQ problem itself, nor plain UOV; it exploited Rainbow’s specific layered structure, which turned out to leak more than its designers realized. Rainbow was withdrawn from standardization.
Where the family stands.#
The lesson the community drew was to retreat toward the more conservative, less structured UOV. As of this writing, several multivariate signatures – UOV itself, MAYO (a UOV variant with a smaller key, using a “whipping” technique to reuse a compact map), and QR-UOV (a quotient-ring variant that compresses the key) – are candidates in NIST’s additional-signatures “on-ramp” process, the round opened specifically to broaden the signature portfolio beyond the lattice and hash standards. None of them is a FIPS standard, and the process is ongoing; their standing may change.
24.5Trade-offs and status#
Multivariate signatures occupy a very particular corner of the design space, and Table 24.1 lays out the shape of the bargain. The signatures are extraordinarily small – often tens to a couple of hundred bytes, competitive with or smaller than pre-quantum ECDSA – and verification, being a batch of polynomial evaluations, is fast. The price is the public key, which stores the coefficients of \(m\) quadratics in \(n\) variables. That is roughly \(m \cdot n^2 / 2\) field elements, growing quadratically with the dimension, so public keys run from tens of kilobytes to over a megabyte, and there is no seed that regenerates them, for the same reason as in the code-based case: a compressible public key would carry structure an attacker could exploit. Key-generation cost and the absence of a KEM round out the profile.
| Property | Multivariate signatures (UOV family) |
|---|---|
| Primitive | signatures only (no practical KEM) |
| Signature size | very small (tens to a few hundred bytes) |
| Public key size | very large (tens of KB to \(>1\) MB) |
| Verification | fast (evaluate public quadratics) |
| Signing | moderate (invert the central map) |
| Hardness assumption | MQ: solving random multivariate quadratics |
Status.#
No multivariate scheme is among the FIPS standards (ML-KEM, ML-DSA, SLH-DSA, FN-DSA); those are drawn from the lattice and hash families. Rainbow, the family’s most prominent standardization candidate, was broken in 2022 and withdrawn. The conservative core, UOV, together with the more compact variants MAYO and QR-UOV, is under evaluation in NIST’s additional-signatures round as of this writing, with the outcome not yet settled. The practical appeal, if these schemes are standardized, is a niche but real one: settings where signatures are transmitted or stored constantly but the public key is distributed rarely, so that a small signature matters far more than a large key.
24.6Pitfalls#
Pitfall 1: assuming a structured trapdoor is safe because MQ is hard.#
This is the defining hazard of the family, and Rainbow is its cautionary tale. The public key is not a random MQ instance – it is \(S \circ F \circ T\), and the hidden structure of \(F\) can leak through the linear disguise. Attacks like Kipnis–Shamir on balanced oil-and-vinegar and Beullens on Rainbow [4] never solved MQ in general; they detected and peeled away the specific structure of the central map. The more structure a variant adds to shrink its keys, the more an attacker has to grip. Security rests on the disguised system being indistinguishable from random, and that must be argued for each construction, not inherited from the NP-hardness of MQ.
Pitfall 2: forgetting that the public key is large and incompressible.#
Unlike the lattice standards, whose public matrix expands from a 32-byte seed, a multivariate public key is a dense list of quadratic coefficients with no shorter description. Budgeting for it as if it were a few kilobytes, or planning to ship it inside every handshake, will not work. The family suits scenarios where the key is installed once and reused, not renegotiated per session.
Pitfall 3: using a balanced or under-parameterized oil-and-vinegar split.#
Plain balanced oil and vinegar (\(v = o\)) is broken. Security requires an unbalanced split with substantially more vinegar than oil, and the exact ratio and field size are load-bearing parameters, not free choices. Under-sizing them re-opens the very attacks the unbalanced design was introduced to close.
Pitfall 4: expecting a KEM.#
The trapdoor is easy to evaluate and hard to invert, which is the right shape for signing and the wrong shape for public-key encryption. Multivariate encryption schemes have a poor security track record; if you need post-quantum key establishment, reach for a lattice or code-based KEM, not this family.
24.7Summary#
Multivariate cryptography is the fourth of the post-quantum families this book surveys, and it rests on the MQ problem: solving a system of multivariate quadratic equations over a finite field, an NP-hard task with no known quantum shortcut beyond Grover’s mild square-root erosion [1]. It is turned into a signature scheme by the now-familiar trapdoor manoeuvre:
start from a central map \(F\) with special structure – classically the oil-and-vinegar form – that can be inverted by linearization;
disguise it between two secret linear maps and publish \(P = S \circ F \circ T\), an explicit system of quadratics that looks random;
anyone can verify by evaluating \(P\), but only the trapdoor holder can sign by inverting it;
accept a very large public key in exchange for an unusually small signature and fast verification – and no KEM.
The family’s history is a lesson in the fragility of structured trapdoors: the balanced oil-and-vinegar scheme fell, and the layered Rainbow, a NIST third-round finalist, was broken by Beullens in 2022 [4], both by attacks that exploited structure rather than by any progress against MQ itself. The response has been a retreat to the conservative core, UOV, and its compact relatives MAYO and QR-UOV, which are under evaluation in NIST’s additional-signatures round as of this writing.
Placed among the five post-quantum families – lattices, codes, hashes, multivariate systems, and isogenies – multivariate cryptography is the specialist of the group: signature-only, smallest-in-class signatures, largest-in-class keys, and a hard-won reputation for caution after some public failures. Crucially, and unlike the lattice and hash families that supply today’s FIPS standards, it has no standardized scheme yet. It remains a live and valuable hedge – an independent hard problem held in reserve – but one still proving, candidate by candidate, that its trapdoors can withstand the scrutiny that broke its predecessors.
Comments