Computational cryptography › Multivariate
SIGNATUREPrimitiveHistorically broken

Rainbow

In plain words

A quantum-safe signature that reached NIST's final round, then was broken in 2022.

The idea: Rainbow was oil-and-vinegar with extra layers to save space. The layers were exactly what the 2022 attack exploited, which is why its plainer parent, UOV, survived.

Why it matters: Its simpler parent, UOV, survived.

The details

On the map: ✗ NIST round-3 finalist

A NIST round-3 finalist signature, broken by Beullens in 2022 before standardization[1, 2]. Its parent scheme, UOV, wasn't affected.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Nothing on the map depends on it: it is an end point, something people use directly.

References

  1. Ward Beullens. Breaking Rainbow Takes a Weekend on a Laptop. Advances in Cryptology – CRYPTO 2022. doi:10.1007/978-3-031-15979-4_16
  2. Gorjan Alagic, Daniel Apon, David Cooper et al. Status report on the third round of the NIST Post-Quantum Cryptography Standardization process. National Institute of Standards and Technology (U.S.), 2022. doi:10.6028/NIST.IR.8413-upd1