https://eprint.iacr.org/2022/214

Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / multivariate
cryptography, cryptanalyis, NIST PQC, Rainbow

Date: received 21 Feb 2022, last revised 25 Feb 2022

Contact author: ward at beullens com

Available format(s): PDF | BibTeX Citation

Version: 20220225:202640 (All versions of this report)

Short URL: ia.cr/2022/214

---------------------------------------------------------------------
[ Cryptology ePrint archive ]