Paper 2022/214

Breaking Rainbow Takes a Weekend on a Laptop

Ward Beullens

Abstract

This work introduces new key recovery attacks against the Rainbow signature scheme, which is one of the three finalist signature schemes still in the NIST Post-Quantum Cryptography standardization project. The new attacks outperform previously known attacks for all the parameter sets submitted to NIST and make a key-recovery practical for the SL 1 parameters. Concretely, given a Rainbow public key for the SL 1 parameters of the second-round submission, our attack returns the corresponding secret key after on average 53 hours (one weekend) of computation time on a standard laptop.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
multivariate cryptographycryptanalyisNIST PQCRainbow
Contact author(s)
ward @ beullens com
History
2022-02-25: last of 2 revisions
2022-02-25: received
See all versions
Short URL
https://ia.cr/2022/214
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/214,
      author = {Ward Beullens},
      title = {Breaking Rainbow Takes a Weekend on a Laptop},
      howpublished = {Cryptology ePrint Archive, Paper 2022/214},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/214}},
      url = {https://eprint.iacr.org/2022/214}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.