International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Breaking Rainbow Takes a Weekend on a Laptop

Authors:
Ward Beullens , IBM Research, Zurich
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Award: Best Paper by Early Career Researcher Award
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 dramatically 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 public key after on average 53 hours (one weekend) of computation time on a standard laptop.
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32130,
  title={Breaking Rainbow Takes a Weekend on a Laptop},
  publisher={Springer-Verlag},
  author={Ward Beullens},
  year=2022
}