← Back to Blog Cryptography

Multivariate Cryptography After Rainbow

10 min read

Multivariate cryptography is the family of public-key schemes whose security rests on the difficulty of solving systems of multivariate quadratic equations over finite fields. The problem itself, called MQ for Multivariate Quadratic, is NP-hard in general. The promise has always been: NP-hard problems should resist quantum attack, so multivariate schemes should be quantum-safe. The reality has been: every standardised multivariate scheme has eventually fallen to a structural attack, including Rainbow, which Ward Beullens broke in 2022.

The post-Rainbow landscape is interesting. Multivariate cryptography is not dead. It is wounded, more cautious, and producing a new generation of designs that explicitly account for what went wrong before. NIST's signature on-ramp (2023) accepted UOV, MAYO, SNOVA, and other multivariate candidates for evaluation. This article walks through the family tree, the lessons of past breaks, and where multivariate cryptography stands in 2026.

The Sudoku Designer

Imagine a Sudoku puzzle designer who specialises in puzzles that are easy for the designer (because they remember how they constructed the puzzle) but hard for everyone else (because the construction is hidden). To convince you the puzzle is solvable, they show you the completed grid (the public key) but hide the construction trick (the private key). Your job is to find a fresh solution to a similar puzzle. Without the trick, this is hard. With the trick, it is fast.

Multivariate cryptography is the cryptographic version of this puzzle designer. The "puzzle" is a system of quadratic equations. The "construction trick" is a layered structure (oil and vinegar) that makes the system efficiently solvable for whoever built it. The public key is the equations themselves; the private key is the layering.

The trouble with this metaphor, and with multivariate cryptography in practice, is that the layering tends to leave fingerprints. Smart cryptanalysts find ways to detect the fingerprints, and once detected, the layering can be peeled apart. Patarin's C* scheme, HFE, SFLASH, and Rainbow all eventually fell to attacks that recognised the layering pattern.

The Multivariate Family Tree

Multivariate cryptography traces back to Tsutomu Matsumoto and Hideki Imai's 1988 paper, "Public quadratic polynomial-tuples for efficient signature-verification and message-encryption". Their scheme, called C* or Matsumoto-Imai, was elegant but fell to Patarin's 1995 attack. Patarin then proposed several successors:

HFE (Hidden Field Equations), 1996: A trapdoor based on hidden univariate equations over an extension field, then converted to a multivariate system. Studied for decades; some parameter sets fell, others survived with adjustments.
UOV (Unbalanced Oil and Vinegar), 1997: A signature scheme based on partitioning variables into "oil" and "vinegar" classes. The original Oil and Vinegar was broken in 1998 by Kipnis and Shamir; UOV was the unbalanced fix that has held up.
Rainbow, 2005: A multi-layer generalisation of UOV. NIST Round 3 finalist. Broken by Beullens in 2022.

Other multivariate proposals over the years:

SFLASH (NESSIE 2003): A C*-derived scheme. Broken by Dubois, Fouque, Shamir, Stern in 2007.
PMI: Polynomial-based multivariate identification. Broken.
GeMSS: A NIST Round 2 HFE variant. Eliminated for performance and size, not security.
SNOVA: A NIST signature on-ramp Round 1 candidate. Noisy oil-and-vinegar variant.
MAYO: Beullens's own post-Rainbow design. NIST signature on-ramp Round 1 candidate.

The family is large, and the cryptanalytic record is mixed. Some branches (UOV) have survived; others (C*, Rainbow) have fallen.

The Oil-and-Vinegar Trick

UOV and its descendants (Rainbow, MAYO) all use the oil-and-vinegar partition. Here is the simplified idea:

The signer has n variables: some called "oil" (denoted O) and some called "vinegar" (denoted V). The public-key equations are quadratic in all n variables. But the signer secretly knows which variables are oil and which are vinegar. When signing, the signer:

Picks random values for the vinegar variables.
Substitutes those values into the equations.
The remaining oil variables now appear in linear equations (because oil*oil terms are missing by construction).
Solves the linear equations to find oil values.
The full vector (vinegar + oil) is the signature.

The catch: oil*oil terms must be missing from the original equations, which constrains the public key shape. Rainbow's break exploited this constraint to peel apart the oil-and-vinegar layering.

What Beullens Did

Ward Beullens's 2022 attack on Rainbow ("Breaking Rainbow Takes a Weekend on a Laptop") exploited the multi-layer structure of Rainbow specifically. UOV with a single layer is harder to attack because there is less structure to peel. Rainbow added more layers to get smaller signatures, which inadvertently gave the attacker more places to attach.

Beullens's attack on Rainbow Category 3 (the SL-3 parameter set) ran in approximately 2^53 operations, far below NIST's claimed 2^192 security level. Rainbow Category 5 fell at 2^85.

UOV at the same security levels was not affected. Single-layer UOV continues to be considered secure.

For more detail on the Rainbow break, see Rainbow Broken Explained.

What Survives: UOV, MAYO, SNOVA

After Rainbow's elimination from NIST Round 3 (July 2022), the multivariate community pivoted to schemes that explicitly avoid Rainbow's layered structure. NIST's signature on-ramp call (June 2023) explicitly invited new signature candidates, and several multivariate proposals were submitted:

UOV: Plain unbalanced oil-and-vinegar at modern parameter sizes. Larger signatures than Rainbow but more conservative.
MAYO (Beullens, Campos, Celi, Hess, Kannwischer, 2021-2023): A modification of UOV that compresses public keys via a clever variable reduction. Smaller keys than UOV without sacrificing security.
SNOVA (Wang, Sayer, Yang, Petzoldt, 2022): "Simple Noisy Oil and Vinegar". Adds noise to the public-key construction to defend against algebraic attacks.
PROV: A UOV variant with provable security under a stronger assumption.
TUOV: Triangular UOV.
3WISE: A different multivariate construction.

NIST is currently evaluating these and other candidates. The signature on-ramp is expected to take several years; final selections are not expected before 2026 or 2027.

The MAYO Story

MAYO is interesting because Ward Beullens, the same researcher who broke Rainbow, co-designed it. Beullens explicitly wrote about the lessons from his own attack and how MAYO avoids the structural weaknesses he exploited. The defensive design includes:

No multi-layer structure: MAYO uses a single-layer UOV variant.
Compressed public keys: A different technique (whipped UOV) reduces public key size without adding layered structure.
Tighter parameter analysis: MAYO's security analysis explicitly accounts for the attack vectors that hit Rainbow.

This kind of "design with awareness of past breaks" is the multivariate community's response to its track record. Whether it produces a survivor remains to be seen.

Multivariate Strengths and Weaknesses

The multivariate family has clear strengths:

Tiny signatures: 60 to 200 bytes are typical. ML-DSA signatures are 2-4 KB. SLH-DSA signatures are 8-50 KB.
Fast verification: A few thousand finite-field multiplications. ML-DSA needs polynomial multiplications and number-theoretic transforms.
NP-hard underlying problem: The MQ problem is provably NP-hard.
Different math from lattices: Provides cryptographic diversity.

And clear weaknesses:

Track record of breaks: C*, SFLASH, Rainbow, PMI, several others. Cryptographic history is full of multivariate failures.
Large public keys: 50 KB to 1 MB depending on parameters. ML-DSA public keys are 1-2 KB.
No NIST FIPS standard: As of 2026, no multivariate scheme is NIST-standardised. The signature on-ramp has not concluded.
Side-channel vulnerabilities: Multivariate schemes have had a difficult relationship with constant-time implementation; signing involves solving equations whose timing can leak information.

For 2026 deployment, multivariate cryptography is a research-grade option. Production systems should default to ML-DSA (lattice), SLH-DSA (hash), or FN-DSA (lattice) for signatures. See ML-DSA vs SLH-DSA and FN-DSA Explained.

The Diversity Argument

Even with the track record, multivariate cryptography is worth keeping alive in research. The reasoning is the same as for non-lattice KEMs: cryptographic diversity matters. If lattices ever fall, the world needs a non-lattice signature scheme that has been studied long enough to deploy with confidence.

NIST's portfolio includes hash-based signatures (SLH-DSA, LMS, XMSS) for exactly this purpose. Hash-based signatures have an even longer track record and a simpler security argument than multivariate. So the multivariate niche is narrower than just "post-quantum diversity"; it is "compact diversity" for scenarios where signature size matters and hash-based signatures are too big.

Multivariate Cryptography in QNSQY

QNSQY does not ship multivariate signatures. The product policy is FIPS-only for post-quantum primitives, and no multivariate scheme has FIPS standardisation in 2026. The signature portfolio is ML-DSA (FIPS 204), SLH-DSA (FIPS 205), FN-DSA (FIPS 205 draft), and LMS (NIST SP 800-208).

If MAYO, UOV, or SNOVA achieves NIST FIPS standardisation through the signature on-ramp, QNSQY will evaluate adding it. The signature on-ramp is unlikely to conclude before 2027 at the earliest, so multivariate is not on QNSQY's near-term roadmap.

For customers asking "why no multivariate?", the answer is the Rainbow lesson. A scheme that loses 100 bits of security in a weekend on a laptop is too risky for hospital and military-grade deployment. The post-Rainbow generation (MAYO, UOV) may eventually clear that bar, but they have not yet.

When Small Signatures Matter

The case for multivariate cryptography is strongest in scenarios where signature size dominates other costs. A few examples:

TLS handshakes with constrained clients: Embedded devices that buffer the entire handshake in RAM benefit from compact signatures. A 100-byte multivariate signature versus a 3 KB ML-DSA signature could matter on a Cortex-M0 with 16 KB of RAM.
High-volume signing services: A document timestamping service that signs millions of attestations per day cares about per-signature byte cost.
Bandwidth-constrained protocols: Satellite firmware updates or tactical radio mesh networks where every byte costs energy.

Hash-based signatures (SLH-DSA at 8-50 KB, LMS at 1-3 KB) and lattice signatures (ML-DSA at 2-4 KB, FN-DSA at 0.7-1.3 KB) cover most of these scenarios already. FN-DSA is particularly competitive at 690 bytes for FN-DSA-512. The remaining niche where multivariate signatures could win is the sub-200-byte regime, where no FIPS-standardised scheme currently lives. If MAYO or UOV reaches FIPS standardisation, that niche could open up.

Frequently Asked Questions

Are all multivariate schemes broken?

No. Rainbow is broken, but UOV and several post-Rainbow designs (MAYO, SNOVA) are not. The multivariate family has a higher break rate than lattice or hash-based families, but the surviving candidates are still considered secure at appropriate parameter sets.

Could MAYO be broken the same way Rainbow was?

The MAYO design explicitly avoids Rainbow's multi-layer structure, which was the basis of the Beullens attack. MAYO uses a single-layer UOV variant with whipped key compression. As of 2026, no successful attack on MAYO has been published, and the design team includes the researcher who broke Rainbow, suggesting a defensive design awareness.

Why does NIST keep evaluating multivariate signatures?

For diversity. NIST's signature on-ramp is explicitly looking for non-lattice, non-hash signature schemes that could complement ML-DSA, SLH-DSA, and FN-DSA. Multivariate is one of the few families with a real chance of producing such an alternative. Whether any multivariate scheme will pass the on-ramp evaluation remains to be seen.

What is the smallest multivariate signature?

UOV at NIST Category 1 produces signatures around 100 bytes. MAYO is similar. Compared to ML-DSA's ~2.5 KB or SLH-DSA's ~8 KB, multivariate signatures are an order of magnitude smaller. This is the main reason the family stays interesting despite the track record of breaks.

Sources

NIST. "Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process." June 2023. https://csrc.nist.gov/projects/pqc-dig-sig
Beullens, W. "Breaking Rainbow Takes a Weekend on a Laptop." IACR ePrint 2022/214. https://eprint.iacr.org/2022/214
Patarin, J. "The Oil and Vinegar Signature Scheme." Dagstuhl Workshop, 1997. https://www.minrank.org/oilnvinegar.pdf
Beullens, W., Campos, F., Celi, S., Hess, B., Kannwischer, M. J. "MAYO: Multivariate Quadratic with Whipping." IACR ePrint 2023/766. https://eprint.iacr.org/2023/766
NIST. "Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process." NIST IR 8413, July 2022. https://csrc.nist.gov/pubs/ir/8413/final
Matsumoto, T., Imai, H. "Public quadratic polynomial-tuples for efficient signature-verification and message-encryption." EUROCRYPT 1988. https://link.springer.com/chapter/10.1007/3-540-45961-8_39

Protect Your Data Before Q-Day Arrives

QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.

Try QNSQY