Multivariate Cryptography
Multivariate cryptography is a family of post-quantum cryptography whose security rests on the hardness of solving systems of multivariate quadratic equations over a finite field, a problem known as the MQ problem that stays hard for both classical and quantum computers. It’s the family with the most distinctive tradeoff in the whole field: it produces some of the shortest signatures anywhere in post-quantum cryptography, and it pays for them with public keys that are enormous. It’s also the family with the most instructive scar. Its flagship signature scheme, Rainbow, was a NIST finalist until Ward Beullens broke it on a laptop in 2022, which is why NIST is re-examining the family through its additional-signatures on-ramp rather than counting it among the algorithms it has already standardized.
The short version:
- Multivariate cryptography secures data on the difficulty of the MQ problem, finding values that satisfy a big system of multivariate quadratic equations over a finite field, a foundation completely separate from lattice or code-based math.
- It’s a signature family, and its calling card is size: very short signatures paired with very large public keys, which is close to the inverse of the elliptic-curve signatures it would replace.
- It resists Shor’s algorithm because the MQ problem has none of the periodic, number-theoretic structure Shor’s needs to break RSA and elliptic-curve cryptography.
- Its cautionary history is central: Rainbow, a NIST Round 3 finalist, was broken by Ward Beullens in 2022 in about 53 hours on a standard laptop, which knocked the family’s headline scheme out of contention.
- NIST has not standardized a multivariate scheme. Several survivors (UOV, MAYO, QR-UOV, SNOVA) are being re-examined in NIST’s additional-signatures process, so the family is best read as a diversification bet with a mixed record, alongside hash-based cryptography as a non-lattice option.
Picture being handed a few thousand quadratic equations in several hundred unknowns, all tangled together over a finite field, and asked to find one assignment of values that satisfies every equation at once. With no hidden structure to exploit, that search is brutal, and it gets worse fast as the number of variables climbs. The person who built the puzzle holds a secret, well-behaved version of the same equations that collapses the tangle into something solvable in one pass. Everyone else sees a public version that’s been scrambled until it looks like random noise. To sign a message, the holder uses the secret structure to produce a tiny answer; to verify, anyone plugs that answer back into the public equations and checks that it fits. A quantum computer doesn’t hand an attacker the secret structure.
How does multivariate cryptography work?
Multivariate cryptography builds a signature scheme out of a public map of quadratic equations that’s easy to check and hard to invert. The public key is a system of multivariate quadratic polynomials over a finite field, usually written as a map that takes an input vector of field elements to an output vector. Verifying is just evaluating that map, which is fast arithmetic. Inverting it without the trapdoor means solving the MQ problem, and solving a general system of multivariate quadratic equations over a finite field is NP-hard, with the decision version NP-complete.
Source: M. Garey and D. Johnson, Computers and Intractability, W.H. Freeman, 1979, the classic reference establishing the NP-completeness of solving quadratic systems over a finite field.
The trapdoor is what makes the scheme usable, and the Oil-and-Vinegar design is the one that survived. It splits the variables into two groups, the “oil” variables and the “vinegar” variables, and structures the secret equations so that once the vinegar variables are fixed to random values, the system becomes linear in the oil variables and solves instantly. The signer scrambles that friendly structure with secret linear transformations before publishing, so the public map looks structureless. The mechanism has a consistent shape:
- Key generation. The signer picks a central map with the hidden oil-and-vinegar structure that’s easy to invert, then composes it with secret invertible linear transformations. The scrambled composition is the public key; the transformations plus the central map are the private key.
- Signing. To sign a message, the signer hashes it to a target vector in the output space, then uses the private trapdoor to find an input vector the public map sends to that target. Because the trapdoor turns the hard inversion into fixing the vinegar variables and solving a linear system, this is fast, and the resulting signature is a short vector of field elements.
- Verification. Anyone evaluates the public quadratic map on the signature and checks that it lands on the hash of the message. If it does, the signature is valid, because only someone with the trapdoor could have produced a preimage.
There’s no factoring and no discrete logarithm anywhere in this, which is exactly why Shor’s algorithm has nothing to attack. The scheme’s most-studied and most-durable instance is the Unbalanced Oil and Vinegar scheme (UOV), introduced by Kipnis, Patarin, and Goubin in 1999, which uses many more vinegar variables than oil variables to resist the attack that had broken the original balanced design.
Source: A. Kipnis, J. Patarin, and L. Goubin, “Unbalanced Oil and Vinegar Signature Schemes,” Eurocrypt 1999, SpringerLink.
Why are the signatures so small but the public keys so large?
The size profile falls straight out of the construction. A signature is just an input vector to the public map, a short list of finite-field elements, so multivariate schemes produce some of the smallest signatures in all of post-quantum cryptography, often a few dozen to a few hundred bytes. The public key is the whole quadratic map, and describing a system of quadratic equations in hundreds of variables takes a coefficient for every pairwise product of variables, so the key grows roughly with the square of the number of variables. That pushes public keys into the tens or hundreds of kilobytes.
That inverse profile decides where the family fits. It’s attractive wherever a signature is transmitted or stored constantly and the verifying key can be provisioned once and reused, because you pay the large public key a single time and enjoy tiny signatures forever after. It’s a poor fit wherever fresh public keys ship on every connection, since the large key then dominates the bandwidth on each handshake. This is close to a mirror image of the lattice signature standards, where keys and signatures are both moderate, and it’s the reason NIST’s interest in the family is specifically about the short-signature, fast-verification corner of the design space.
Source: NIST, “Post-Quantum Cryptography, Digital Signature Schemes,” project page, which states NIST’s particular interest in additional general-purpose signatures with short signatures and fast verification not based on structured lattices, csrc.nist.gov.
What happened to Rainbow, and why did it get broken?
Rainbow was a multivariate signature scheme, a layered generalization of Unbalanced Oil and Vinegar, and it advanced all the way to Round 3 of NIST’s main post-quantum competition as one of the three finalist signature schemes. In February 2022, Ward Beullens of IBM Research published a new key-recovery attack that exploited the extra algebraic structure Rainbow’s layers introduced. For the level-1 parameter set of Rainbow’s second-round submission, his attack recovered the secret key in about 53 hours, one weekend, on a standard laptop.
Source: W. Beullens, “Breaking Rainbow Takes a Weekend on a Laptop,” IACR ePrint 2022/214, 2022, eprint.iacr.org.
The break mattered beyond Rainbow itself for two reasons. It removed the family’s most prominent candidate from the standardization it was on the verge of reaching, and it did so with an attack that ran on commodity hardware over a weekend, not a state-scale supercomputer, which is the most vivid kind of cryptographic failure. It also reinforced the field’s hardest lesson: extra algebraic structure added for efficiency is also extra surface for an attacker to grab. The plainer Unbalanced Oil and Vinegar design that Rainbow was built on top of was not broken by this attack and remains under active study, which is why the family survived the loss of its flagship rather than disappearing with it.
Where does multivariate cryptography stand in NIST standardization today?
NIST has not standardized any multivariate scheme. After finalizing its lattice and hash-based signature standards, NIST recognized that leaning heavily on structured lattices was a concentration, and in September 2022 it issued a call for additional post-quantum signatures, with particular interest in general-purpose schemes not based on structured lattices. The call closed on June 1, 2023.
Source: NIST, “Post-Quantum Cryptography, Digital Signature Schemes,” project page, csrc.nist.gov.
In October 2024, NIST published its first-round status report and advanced 14 candidates to the second round. Four of them are multivariate, which is where the family’s current hopes sit:
| Scheme | Family basis | Notable trait | NIST status |
|---|---|---|---|
| UOV | Unbalanced Oil and Vinegar | The most-studied multivariate design; very short signatures, large public key | Round 2 candidate (Oct 2024) |
| MAYO | Oil-and-Vinegar variant with a “whipped” map | Shrinks the UOV public key toward practical sizes | Round 2 candidate (Oct 2024) |
| QR-UOV | Quotient-ring UOV | Uses ring structure to compress the public key | Round 2 candidate (Oct 2024) |
| SNOVA | Noncommutative-ring UOV variant | Compact keys via a noncommutative algebraic structure | Round 2 candidate (Oct 2024) |
Source: NIST IR 8528, Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process, October 2024, csrc.nist.gov.
So the honest status is that multivariate cryptography is a family NIST is still evaluating, on a separate and slower track from the finalized standards, and none of its schemes is deployable as an approved standard yet. Anyone building today reaches for ML-DSA or SLH-DSA, and watches the multivariate round as a possible future option for the short-signature niche.
How does it compare to the other post-quantum families?
Multivariate cryptography is best understood as one of several diversification bets, valued for resting on math that a break in the mainline standards wouldn’t touch. Its distinguishing traits are the tiny signatures, the large keys, and the mixed track record that comes from having its most famous scheme fall.
| Family | What it does | Security basis | Track record | Signature size |
|---|---|---|---|---|
| Lattice | KEM and signatures | Module-LWE and lattice geometry | Well-studied, the standardized mainline | Moderate |
| Code-based | Key establishment | Decoding random linear codes | Longest unbroken record, since 1978 | (no signature) |
| Hash-based | Signatures | Strength of a hash function | Most conservative assumption | Large |
| Multivariate | Signatures | The MQ problem over a finite field | Mixed; Rainbow broken 2022, UOV survives | Very small |
The comparison makes the case for and against the family in one view. On the plus side, its signatures are the smallest around and its security assumption is genuinely independent of lattices, so it would be a useful hedge in a diversified portfolio. On the minus side, the Rainbow break is a real reminder that multivariate designs can carry hidden structure that turns into a practical attack, so the family carries less settled confidence than hash-based cryptography, whose worst case is far better understood. Keeping more than one independent family in view is the instinct behind crypto-agility, and multivariate cryptography is one of the candidates that instinct keeps on the table.
Common misconceptions
“Multivariate cryptography is a NIST standard.” It isn’t. No multivariate scheme has been standardized. UOV, MAYO, QR-UOV, and SNOVA are second-round candidates in NIST’s separate additional-signatures process, which is still ongoing, so the family is a design-for and watch-closely option, not a deploy-today one.
“The whole family is broken because Rainbow fell.” Only Rainbow’s specific layered structure was broken by Beullens in 2022. The plainer Unbalanced Oil and Vinegar design it built on was not, and UOV and its variants remain under active evaluation. The break narrowed the family; it didn’t end it.
“Multivariate schemes can do encryption and key exchange.” The durable, well-studied multivariate constructions are signature schemes. Multivariate encryption has been tried and has a rough history of breaks, so the family’s realistic role in the transition is signing, not key establishment.
“Small signatures mean small everything.” Signature size and key size are separate axes here, and they point in opposite directions. Multivariate schemes give you very short signatures precisely alongside very large public keys, which is the defining tradeoff to plan around.
“If a laptop broke it, the math must be weak.” The Rainbow attack exploited the extra algebraic structure of that specific scheme, not a weakness in the general MQ problem, which remains NP-hard. The lesson the field took was about the danger of structure added for efficiency, not about multivariate hardness being fragile in general.
Questions people ask
Is multivariate cryptography quantum-safe? As far as current science shows, the MQ problem underneath it has no known efficient quantum attack. Shor’s algorithm relies on periodic structure that multivariate systems don’t have, and Grover’s algorithm offers only a generic search speedup that parameter sizes account for. The live risk for this family is classical algebraic cryptanalysis, the kind that broke Rainbow, rather than quantum computing.
Can I deploy a multivariate signature scheme today? Not as an approved standard. The multivariate candidates are in the second round of NIST’s additional-signatures evaluation with no finalized standard, so production systems use the finalized signatures (ML-DSA and SLH-DSA) and treat multivariate as a future possibility.
Why would anyone want multivariate cryptography given the Rainbow break? Two reasons: its signatures are the smallest in post-quantum cryptography, which matters where signatures are transmitted constantly, and its security rests on math wholly independent of lattices, so it diversifies risk. The Rainbow break is exactly why NIST is studying the survivors carefully before standardizing any of them.
What is the MQ problem? It’s the problem of finding an assignment of variables that satisfies a system of multivariate quadratic equations over a finite field. In general it’s NP-hard, with the decision version NP-complete, and that hardness is the foundation the whole family stands on.
What is Unbalanced Oil and Vinegar? UOV is the most-studied and most-durable multivariate signature design, introduced by Kipnis, Patarin, and Goubin in 1999. It structures the secret equations so that fixing the “vinegar” variables makes the system linear in the “oil” variables and easy to solve, using many more vinegar variables than oil variables to resist earlier attacks. Most of the surviving multivariate candidates are UOV variants.
Does multivariate cryptography help with encryption or just signatures? In practice, just signatures. The well-studied, still-standing multivariate schemes are signature schemes, and multivariate encryption attempts have generally not held up, so the family’s role in the transition is on the signing side.
How does its signature size compare to lattice and hash-based signatures? Multivariate signatures are the smallest of the three, often a few dozen to a few hundred bytes. Lattice signatures like ML-DSA are moderate, and hash-based signatures like SLH-DSA are large. The catch is that multivariate pays for its tiny signatures with a public key far larger than either of the others.
Multivariate cryptography is the family you keep an eye on for the short-signature niche while remembering that its most famous scheme fell on a laptop, and understanding it explains both why NIST wants a non-lattice signature option and why it’s being so careful before standardizing one. Everything here is the map, given freely. When your team needs to decide which post-quantum signatures actually belong in your protocols and estate, that’s what an alignment briefing is for.
Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.