When the Finalists Fall: What Rainbow and SIKE Taught Us About Post-Quantum Standardisation

Cryptographic standardisation is usually presented as a process of selecting winners. Candidates are submitted, experts evaluate them, weaker designs are eliminated, and the strongest algorithms eventually become standards. The NIST Post-Quantum Cryptography standardisation process followed this general pattern, but with an unusual and important twist: two serious candidates survived almost until the end, only to suffer devastating cryptanalytic breaks. Rainbow was effectively eliminated late in the third round, while SIKE was broken shortly after advancing to the fourth round. And by this time already several years of research was done.

To me, these events are among the most remarkable aspects of the entire NIST process. They demonstrate both how difficult it is to evaluate new cryptographic assumptions and why public cryptanalysis must remain at the centre of cryptographic standardisation.

A global experiment in cryptanalysis

NIST began its post-quantum standardisation project because the public-key systems used today, particularly RSA and elliptic-curve cryptography, would be vulnerable to a sufficiently capable quantum computer. The objective was therefore to identify algorithms that could replace current public-key encryption, key-establishment and digital-signature mechanisms.

The formal call for proposals was published in December 2016. By the end of 2017, NIST had accepted 69 algorithms into the first round. The candidates represented several mathematical families, including lattices, error-correcting codes, multivariate polynomial systems, hash-based constructions and isogenies between elliptic curves. The field was reduced to 26 candidates in the second round and then to seven finalists and eight alternate candidates in the third round.

This was not a conventional competition in which an algorithm won by being faster than its rivals. Security was the primary requirement, and security could not be demonstrated by benchmarks alone. Each design had to withstand years of public attacks by cryptographers around the world.

That point is essential. A cryptographic scheme is not considered trustworthy because its designers cannot break it. It becomes trustworthy only after many other researchers have tried and failed.

Rainbow: broken during the final stretch

Rainbow was a multivariate digital-signature scheme. Its security was based on the difficulty of solving specially constructed systems of multivariate quadratic equations. Multivariate cryptography was attractive partly because it provided diversity: unlike several other leading candidates, Rainbow was not based on lattices.

Rainbow reached the third round as a signature finalist. By that stage, it had already survived years of analysis and had been treated as a plausible candidate for standardisation. Then, on 25 February 2022, Ward Beullens published Breaking Rainbow Takes a Weekend on a Laptop. The paper described new key-recovery attacks against the submitted Rainbow parameters. For the level-one parameter set, a private key could be recovered from the public key in an average of approximately 53 hours using an ordinary laptop. The attacks also outperformed the previously known attacks against the higher-security parameter sets.

The title captured the seriousness of the result. An algorithm intended to provide long-term protection against powerful future attackers could be compromised over a weekend using consumer hardware.

There is a technical nuance here. The paper did not show that every Rainbow parameter set could immediately be broken in a few hours. Larger parameters could potentially have been chosen. However, the submitted security claims had collapsed, the efficiency advantages would have been substantially reduced by increasing the parameters, and the attack suggested that the structure of Rainbow was less well understood than previously believed.

In practical standardisation terms, Rainbow was finished. What makes this episode striking is its timing. The attack appeared more than four years after the first-round candidates had been announced and only a few months before NIST completed the third round on 5 July 2022. Rainbow did not fail during an initial screening. It failed after years of research, optimisation and evaluation, while standing close to the finish line.

SIKE: from fourth-round candidate to broken in 25 days

The collapse of SIKE was even more dramatic. SIKE, the Supersingular Isogeny Key Encapsulation mechanism, was based on the SIDH key-exchange protocol. Its underlying mathematics involved isogenies—structure-preserving maps between elliptic curves. Compared with many lattice- and code-based candidates, SIKE offered extremely small public keys and ciphertexts. SIKE was not chosen as one of the first algorithms for standardisation at the end of the third round. Nevertheless, NIST considered its compact keys sufficiently attractive to justify further investigation. On 5 July 2022, NIST advanced SIKE, together with BIKE, Classic McEliece and HQC, into a fourth round of evaluation. NIST specifically identified SIKE’s small key and ciphertext sizes as an important advantage. Only 25 days later, on 30 July 2022, Wouter Castryck and Thomas Decru published an efficient key-recovery attack against SIDH. The attack used mathematical ideas that were very different from the generic attacks previously considered against the underlying isogeny problem. Instead of attacking the most obvious hard problem directly, it exploited additional information exchanged as part of the SIDH protocol.

The results were devastating. The researchers reported that SIKEp434, which targeted NIST’s first security level, could be broken in approximately ten minutes on a single processor core. The attack was not a marginal reduction in security or a warning that parameters should be increased. It fundamentally destroyed the security of the submitted construction. NIST’s fourth-round page now states plainly that SIKE and SIDH are insecure and should not be used. This was an extraordinary reversal. In early July, SIKE was still regarded as sufficiently promising to deserve another round of analysis. Before the end of the same month, its central security mechanism had been broken.

Did the process fail?

It is tempting to interpret these events as evidence that the NIST process failed. How could algorithms survive for so many years and remain candidates so late in the process if they were vulnerable to such powerful attacks?

I think that interpretation is understandable but ultimately mistaken. The purpose of the evaluation process was not to ensure that every candidate entering the later rounds was secure. That would have required knowing the answer before conducting the evaluation. The purpose was to expose candidates to sustained public scrutiny and eliminate designs when serious weaknesses were discovered.

From that perspective, the process worked exactly when it mattered. Rainbow and SIKE were attacked before becoming standards and before they were deployed as the long-term foundations of critical infrastructure. A cryptographic competition in which no candidate is ever broken should not necessarily inspire confidence. It might instead indicate that the candidates did not receive enough attention. At the same time, the late timing should make us uncomfortable. Both cases show that several years without a catastrophic attack do not constitute proof of security. Cryptanalytic progress is not linear. A scheme can survive hundreds of incremental papers and then collapse because one researcher finds a new way of looking at its structure.

Survival is not proof

The Rainbow and SIKE stories illustrate a fundamental problem in cryptography: we generally cannot prove that practical public-key schemes are secure in an absolute sense. We can reduce their security to mathematical problems. We can estimate the complexity of known attacks. We can test implementations and examine side channels. We can compare parameters with the best available algorithms. But an unknown attack remains unknown until someone discovers it. This is particularly relevant for post-quantum cryptography. Some candidate families had decades of study behind them, while others depended on comparatively young assumptions or used old mathematics in new cryptographic ways. Attractive performance characteristics could therefore coexist with considerable uncertainty.

SIKE is perhaps the clearest example. Its tiny keys were valuable precisely because they resulted from a highly specialised construction. Yet that special structure also created an attack surface that was not fully understood. There is no simple formula for balancing innovation against conservatism. Selecting only the oldest constructions may exclude important improvements. Selecting aggressive new designs may expose users to assumptions that have not received enough scrutiny.

[1] Ward Beullens: Breaking Rainbow Takes a Weekend on a Laptop. CRYPTO (2) 2022: 464-479
[2] Wouter Castryck, Thomas Decru: An Efficient Key Recovery Attack on SIDH. EUROCRYPT (5) 2023: 423-447