Computational cryptography › Multivariate
Hardness assumptionHistorically broken

Rainbow trapdoor stays hidden

In plain words

Rainbow stacked extra layers on UOV to save space. In 2022 those layers turned out to be a weakness.

The idea: Rainbow stacked several rounds of oil-and-vinegar on top of each other to shrink keys and signatures. Every layer added structure, and in 2022 Beullens found how to use that structure to recover the private key, for the smallest parameters in a weekend on a laptop.

Why it matters: Another extra assumption that failed while the core problem held.

The details

On the map: ✗ broken 2022 (Beullens): a weekend on a laptop

Rainbow stacked several layers of oil-and-vinegar[1] to be more efficient, adding structure. In 2022 Ward Beullens found an attack[2] exploiting those layers that recovered keys for the smallest parameters in a weekend on a laptop.

Another extra structural assumption that failed while the base problem held.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

References

  1. Jintai Ding and Dieter Schmidt. Rainbow, a New Multivariable Polynomial Signature Scheme. Applied Cryptography and Network Security, 2005. doi:10.1007/11496137_12
  2. Ward Beullens. Breaking Rainbow Takes a Weekend on a Laptop. Advances in Cryptology – CRYPTO 2022. doi:10.1007/978-3-031-15979-4_16