Rainbow (signature scheme)

Rainbow is a post-quantum digital signature scheme built on Multivariate cryptography, meaning its security was meant to rest on the difficulty of solving large systems of multivariate quadratic equations. It was one of three finalists for signatures in round three of the NIST standardization process, but a practical key-recovery attack in 2022 broke it, and it was not standardized.

#How it worked

Rainbow is a layered version of the Unbalanced Oil and Vinegar (UOV) construction. The public key is a set of multivariate quadratic polynomials over a finite field; the private key is a hidden, easily invertible structure (the "oil" and "vinegar" variable split, arranged in two layers) disguised by secret linear transformations. Signing inverts the structured map using the trapdoor, while verification simply evaluates the public polynomials. The appeal of the family is very short signatures, though at the cost of large public keys, the opposite tradeoff from most lattice schemes.

The underlying hard problem, solving a random multivariate quadratic system (the MQ problem), is NP-hard in general and has no known efficient quantum algorithm, which is why multivariate schemes were considered post-quantum candidates alongside lattice, hash-based, and code-based designs.

#The break

The danger of trapdoor multivariate schemes is that the hidden structure can leak. In February 2022 Ward Beullens published a key-recovery attack titled "Breaking Rainbow Takes a Weekend on a Laptop." The attack exploited the layered oil-and-vinegar structure to recover an equivalent private key directly from the public key, and for the first NIST security level it ran in roughly a weekend of computation on a single laptop. This did not attack the generic MQ problem; it exploited the specific structure Rainbow used to build its trapdoor.

The result arrived late in the NIST process, after Rainbow had already reached the finalist round. In its round-three status report (NIST IR 8413), NIST cited the attack as decisive: Rainbow no longer offered the claimed security, so it was not advanced. This echoed the earlier collapse of SIKE, and it reinforced a recurring lesson of the competition: structured trapdoors need years of scrutiny, because a single structural insight can be fatal.

#What survives

The break was specific to Rainbow's layered design, not to multivariate cryptography as a whole. The simpler, single-layer UOV scheme was not affected in the same way, and both UOV and a newer variant called MAYO were submitted to NIST's separate on-ramp call for additional signature schemes, which seeks designs not based on lattices to diversify the standardized portfolio. As of early 2026 these remain under evaluation rather than standardized.

For anyone choosing a signature today, the practical guidance is unchanged: use the standardized schemes. The NIST post-quantum signature standards are ML-DSA and SLH-DSA, with FN-DSA planned; Rainbow is a cautionary example, not a deployment option.