Rainbow

Introduction

Rainbow made it all the way to the third round of NIST’s post-quantum standardization process — a serious multivariate-cryptography signature candidate built on a completely different hard problem from every lattice or hash-based scheme in this series: solving systems of multivariate quadratic equations over a finite field, a problem proven NP-hard in general. Then, in February 2022, Ward Beullens published an attack that broke Rainbow’s proposed security parameters on a single laptop in about a weekend, using a clever algebraic shortcut nobody had previously combined together. Rainbow is included here not despite that break but partly because of it — it’s a genuine, still-instructive lesson in how a promising, mathematically-motivated design can fall to structural cryptanalysis the underlying hardness assumption doesn’t fully protect against.

Table of Contents

• Multivariate Quadratic Systems
• The Oil-and-Vinegar Trick
• Why “Rainbow”: Layering Oil-Vinegar
• Key Generation, Signing, and Verification
• A Worked Example
• The 2022 Break
• FAQ
• References

Multivariate Quadratic Systems

Given a system of quadratic equations in several unknowns over a finite field — like x₁x₂ + 3x₂² + x₃ = 7 and 2x₁x₃ + x₂ = 4 simultaneously — finding a solution is, in general, NP-hard, and even the average case (not just adversarial worst-case instances) has no known efficient algorithm once the number of variables gets large. That’s the raw hardness assumption behind multivariate cryptography: publish a scrambled system of quadratic equations as a public key, and finding any input that satisfies all of them simultaneously (a valid signature) should be computationally infeasible — unless you know a hidden shortcut.

The Oil-and-Vinegar Trick

The shortcut is a 1997 idea called Unbalanced Oil and Vinegar (UOV). Split the variables into two groups: vinegar variables and oil variables. Design the quadratic equations so that oil variables never multiply each other — every quadratic term is either vinegar×vinegar or vinegar×oil, never oil×oil. The payoff: if you fix the vinegar variables to specific (even random) values first, every equation instantly becomes linear in the remaining oil variables — an easy system to solve with ordinary linear algebra. Someone without this vinegar/oil partition sees only a generic, dense-looking quadratic system with no obvious way to fix that trick — that’s the trapdoor.

Why “Rainbow”: Layering Oil-Vinegar

Plain UOV works, but its keys are large for a given security level. Rainbow’s improvement is to chain multiple oil-vinegar layers together: layer 1 has its own vinegar and oil variables; layer 2 treats all of layer 1’s variables (both original vinegar and solved oil) as its vinegar set, with a fresh batch of oil variables of its own; and so on. Solving becomes a cascade — solve layer 1’s small linear system, feed those values in as known “vinegar” for layer 2, solve that linear system, and repeat. Each layer stays small and easy to invert individually, but the overall system uses fewer total variables for the same number of equations than an unlayered UOV scheme would need, which is exactly what “Rainbow” refers to — layers of oil-vinegar stacked like colored bands.

Key Generation, Signing, and Verification

1. Build the central map F: m layered oil-vinegar quadratic polynomials in n variables, as described above (no same-layer oil×oil terms).
2. Generate two random invertible linear maps: T (n×n, disguises the input) and S (m×m, disguises the output).
3. Compute the public key by literally expanding the composition P = S ∘ F ∘ T into its dense quadratic coefficients — the same disguise pattern as McEliece’s S·G·P, just over multivariate polynomials instead of a linear code.
4. To sign a hashed message y: compute y′ = S⁻¹(y), invert the central map layer by layer (pick random vinegar for layer 1, solve linear systems down the cascade) to get x′, then compute the signature x = T⁻¹(x′).
5. To verify: evaluate the public polynomials directly at x (ordinary polynomial evaluation — no knowledge of S, F, T needed) and check the result equals y.

Interactive Visualizer

Real Rainbow uses dozens of variables per layer and a larger field; the visualizer above runs the identical layered-inversion and S/T-disguise structure over GF(31) with a small two-layer split (2 vinegar, 2+2 oil), small enough to watch each linear system get solved directly.

A Worked Example

Using the visualizer’s toy parameters:

1. A random central map (with the correct oil-vinegar zero pattern per layer) and random invertible T, S produce four dense public quadratic polynomials in six variables.
2. To sign, the message hashes to a target y; y′ = S⁻¹y undoes the output disguise.
3. Random vinegar values (x1, x2) are chosen; layer 1’s two equations become a 2×2 linear system in the oil variables (x3, x4), solved directly.
4. All four values (x1-x4) become “vinegar” for layer 2; its two equations become a 2×2 linear system in (x5, x6), solved the same way.
5. T⁻¹ undoes the input disguise, producing the final signature x — which, when plugged into the public polynomials, reproduces y exactly.

The 2022 Break

Beullens’ attack exploited a structural weakness specific to Rainbow’s layered construction: the boundary between consecutive layers introduces a detectable algebraic bias that a well-chosen linear-algebra attack (building on earlier “rectangular MinRank” techniques) could exploit to recover an equivalent private key directly from the public key — without brute-forcing the underlying MQ problem at all. Crucially, this wasn’t a break of multivariate cryptography or the MQ problem in general (plain UOV, without Rainbow’s layering, remains unbroken at the time of writing) — it was specific to how Rainbow chained its layers together, which is precisely why NIST did not select Rainbow for standardization.

FAQ

Does the 2022 attack mean multivariate cryptography as a whole is broken?

No — the attack targeted Rainbow’s specific layered construction, not the underlying multivariate quadratic hardness assumption itself. Plain (single-layer) UOV, which Rainbow was built to improve on, remains an active, unbroken area of multivariate signature research, including newer NIST submissions.

Why include a broken algorithm in an educational series at all?

Because understanding how a well-motivated, competition-finalist design can still fall to structural cryptanalysis — as opposed to a brute-force break of its core hard problem — is one of the most valuable lessons cryptography has to teach, and it’s exactly the kind of nuance a “genuine structure, honestly explained” visualizer is well suited to convey.

How is Rainbow’s public key different from McEliece’s?

Structurally analogous (both hide a fast-invertible trapdoor behind linear scrambling matrices) but built from entirely different mathematical objects — McEliece scrambles a linear error-correcting code’s generator matrix; Rainbow scrambles a system of quadratic polynomials. Attacks that work against one (syndrome decoding attacks for McEliece, MinRank-style attacks for Rainbow) don’t transfer to the other.

Why does fixing the vinegar variables make the system linear?

Because the central map was deliberately designed with zero coefficients on every oil×oil product — once vinegar values are substituted in as constants, every remaining term is either a constant (vinegar×vinegar), or a constant times a single oil variable (vinegar×oil) — nothing multiplies two unknowns together anymore, which is exactly the definition of a linear system.

References

1. Ding, J., Schmidt, D. “Rainbow, a New Multivariable Polynomial Signature Scheme.” ACNS, 2005.

2. Beullens, W. “Breaking Rainbow Takes a Weekend on a Laptop.” CRYPTO, 2022.

3. Kipnis, A., Patarin, J., Goubin, L. “Unbalanced Oil and Vinegar Signature Schemes.” EUROCRYPT, 1999.

4. NIST. “Post-Quantum Cryptography Standardization — Round 3 Additional Signatures.” Available at: https://csrc.nist.gov/projects/post-quantum-cryptography