Multivariate cryptography

Multivariate cryptography builds public-key schemes, in practice almost always digital signatures, on the hardness of solving systems of multivariate quadratic equations over a finite field. That underlying task, called the MQ problem, is NP-hard in general and has no known quantum shortcut. The family is prized for very small signatures and fast verification, but its history is marked by broken schemes.

#The MQ problem and the trapdoor

A multivariate public key is a set of quadratic polynomials in many variables over a small finite field. Evaluating them is cheap, which makes verification fast, but inverting them (finding an input that produces a target output) is the MQ problem, believed hard for both classical and quantum computers. Neither Shor's algorithm, which attacks number-theoretic structure, nor anything better than Grover-type search is known to apply.

Security comes from a trapdoor. The signer starts with a central map that is easy to invert, then hides its structure by composing it with two secret invertible affine transformations. The public polynomials look like a random quadratic system, while the signer alone can run the composition backwards to produce signatures. The recurring danger of the family is that the hiding is imperfect: structural attacks that recover the central map have repeatedly undone specific constructions.

#Oil and Vinegar to Rainbow

The durable idea in the family is Oil and Vinegar, introduced by Jacques Patarin in 1997. The variables split into "oil" and "vinegar" groups arranged so that inversion is easy for the signer. The original balanced version was broken by Kipnis and Shamir in 1998. Unbalanced Oil and Vinegar (UOV), published by Kipnis, Patarin, and Goubin in 1999, restored security by making the vinegar variables substantially outnumber the oil variables, and it has resisted attack in that form for more than two decades.

Rainbow, proposed by Ding and Schmidt in 2005, stacked several UOV layers to shrink keys and signatures. It became the family's flagship: one of three digital-signature finalists in the third round of the NIST standardization process, alongside the lattice schemes that became ML-DSA and FN-DSA.

#The 2022 break of Rainbow

In February 2022, Ward Beullens published a key-recovery attack titled "Breaking Rainbow Takes a Weekend on a Laptop" (IACR ePrint 2022/214). It exploited the extra layered structure Rainbow added on top of UOV, recovering an equivalent private key for the NIST Level 1 parameters in roughly a weekend of computation on a standard laptop. NIST's third-round report recorded the attack and declined to standardize Rainbow (NIST IR 8413). The break was decisive and should be stated plainly: Rainbow, as parameterized for standardization, is broken. This mirrors the isogeny family, where SIDH and SIKE fell to the Castryck-Decru attack in the same year.

#What survives: UOV and MAYO

The attack was specific to Rainbow's layered design and did not touch plain UOV, which Rainbow had been built on top of. With updated parameters, UOV remains one of the most studied and conservative multivariate signatures. When NIST opened a call for additional post-quantum signatures in 2022, explicitly seeking schemes not based on lattices and schemes with short signatures, several multivariate proposals entered (NIST additional signatures).

Two lines advanced into the first round of that onramp. Plain UOV was submitted directly, and MAYO, a UOV variant introduced by Beullens in 2021, shrinks the public key using a "whipping" technique that reuses a small map several times (pqmayo.org). Both are analyzed in NIST's first-round status report on the additional signatures (NIST IR 8528).

#Profile and tradeoffs

The defining characteristic is a lopsided size profile: signatures among the smallest of any post-quantum family, paired with large public keys.

Signatures of a few hundred bytes are far smaller than the lattice-based ML-DSA and dramatically smaller than the hash-based SLH-DSA. The cost is the public key: UOV keys of tens to hundreds of kilobytes rule out contexts that ship a fresh key per connection, while MAYO trades a modest signature increase for keys small enough for ordinary protocols. As with every part of post-quantum cryptography, the value of a distinct mathematical assumption is diversity: if the lattice-based signatures ever weakened, a mature multivariate scheme is a standing alternative with a very different failure mode.