NIST PQC Finalists Update: It’s Over For The Rainbow

Last month, one of the three NIST finalists for post-quantum signature schemes received its final nail in the coffin: Ward Beullens, a PostDoc at IBM Research, published a practical key recovery attack against the Rainbow signature scheme.

The NIST Post-Quantum Cryptography Standardization Process

In 2016, in view of continued advances in quantum computing, and the threat that quantum computers would eventually break essentially all public-key cryptographic algorithms currently in use, the US National Institute of Standards and Technology (NIST) started a multi-year project with the goal to standardize one or more quantum-resistant public-key cryptographic algorithms, for public-key encryption, key establishment, and digital signature algorithms.

Research teams from around the world responded with over 70 submissions of cryptographic schemes, along with parameters to meet three increasing security levels, SL1, SL3, and SL5. Then NIST and the crypto community started with the cryptanalysis. Of the 19 digital signature algorithms accepted for Round 1, nine advanced to Round 2 (January 2019), of which three were announced as Round 3 finalists (July 2020): Dilithium, Falcon, and Rainbow. The NIST Round 3 report to announce which algorithms will be standardized, is expected later this month. Draft standards for public comment are expected in 2022/2023, and the first set of standards should be finalized by 2024. 

Rainbow

Rainbow, based on the so-called Unbalanced Oil and Vinegar scheme, is a multivariate signature scheme, with its security relying on the hardness of the problem of solving a large system of multivariate quadratic equations over a finite field. Just like the RSA signature scheme, Rainbow uses a trapdoor function.

While RSA uses modular exponentiation, Rainbow uses the evaluation of a system of multivariate quadratic polynomials. The trapdoor function’s crucial property is that it can be evaluated very efficiently but is hard to invert, except one knows some (secret) trapdoor information, and then it is just as easy to compute the input of the trapdoor function given its output. This can be used to create a digital signature scheme: To sign a message, one hashes the message and sets that hash as the output of the trapdoor function; the signature then is the input that results in that output.

In the case of Rainbow, the signature of a message is an assignment to the variables that gets evaluated to the hash of that message. For example, for the lowest NIST Round 3 security level, the proposal is to use m=64 polynomials in n=100 variables over the finite field with q=16 elements. In the core of the trapdoor is a linear subspace of the input space (F_q)^n, in which all of the m quadratic polynomials evaluate to zero; with knowledge of this subspace one can solve the system efficiently and forge digital signatures. 

Contrary to the RSA signature scheme, Rainbow is believed to resist the power of large-scale quantum computers. 

Cryptanalysis

Multivariate signature schemes have been around for over 20 years. The problem of solving multivariate equations also arises naturally in other areas of mathematics and computer science, and has generally been well-studied. However, analysis of the specific problem of finding the secret linear subspace in the trapdoor’s core only happened in the years after the proposal of multivariate signature schemes. 

Rainbow’s advancement within the NIST standardization process over the past few years resulted in greatly renewed interest and improved cryptanalysis required, increasing Rainbow’s parameters for NIST’s Round 3. Then, in October 2020, Beullen came up with two new attacks, the Intersection Attack and the Rectangular MinRank Attack, that claimed to dramatically reduce Rainbow’s (theoretical) security. But Beullen’s most recent work seemingly can completely break Rainbow on security level SL1. Specifically, Beullen gives computational proof that his new key recovery attack on Rainbow succeeds and performs as theoretically expected on the NIST Round 2 security parameters at level SL1, and - with credibility - argues this performance carries over to the slightly larger NIST Round 3 parameters. 

What next? 

A drawback of the Rainbow signature scheme compared to Dilithium and Falcon is that the public key is huge, in the order of magnitude of 100s of kilobytes! This has been a significant disadvantage already before Beullen’s work, but the recent attacks now would require even larger key sizes to compensate for the loss in security, if one wanted to salvage Rainbow. The attacks on Rainbow do not apply to Dilithium and Falcon, as their security relies on a mathematically entirely different concept (hard lattice problems). Among Dilithium and Falcon, one will be chosen for the draft standards. B

But who knows what the continued cryptanalysis of these schemes will bring? Whatever algorithms NIST will choose, they might be broken in the future. As the French ANSSI cautions, “the maturity level of the post-quantum algorithms presented to the NIST process should not be overestimated”. 

So, on to Round 4 and a New Call for more signature schemes! Along with the three signature finalists, NIST in 2020 had announced three alternate Round 3 candidates: GeMSS, Picnic, and SPHINCS+. Based on the security of hash functions, SPHINCS+ is considered a sound choice security-wise albeit considerable performance drawbacks, and will potentially be included in the pending Round 3 Report and advance to a 4^th round of evaluation. On top of that, NIST anticipates new promising schemes which were not part of the current PQC standardization project. Indeed, as per NIST’s Dustin Moody at the recent PKC 2022 conference, a new call for signatures will be issued after the conclusion of the 3^rd Round, with the goal to diversify the signature portfolio. 

The need for crypto-agility

The NIST post-quantum signature standardisation process in general, and the cryptanalysis of the Rainbow signature scheme in particular, are timely reminders of the importance of future-proofing your cryptographic use by designing a system that makes switching between cryptographic algorithms simple. One can never be complacent about the life-time of an algorithm – any cryptographic algorithm may have to be replaced over time.  Organizations are well advised to be ‘crypto-agile’: see our recommendations on how to architect a resilient infrastructure.

References and Further Reading

• Breaking Rainbow Takes a Weekend on a Laptop (2022), by
  Ward Beullens, IBM Zürich
• Breaking Rainbow (2022), Ward Beullens, Github
• Understanding NIST’s Process on Post-Quantum Cryptography (PQC) Standardization (2022), by Dawn M. Turner