Breaking Rainbow Takes a Weekend on a Laptop

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 h (one weekend) of computation time on a standard laptop.

Ward Beullens holds Junior Post-Doctoral fellowship 1S95620N from the Research Foundation Flanders (FWO).

A Rank Experiments

Simple Attack. For some rainbow parameter sets over $\mathbb {F}_{31}$ we construct some $\tilde{\mathcal {P}}(\textbf{x}) = 0$ systems as in our simple attack, and compute the ranks of Macaulay matrices of these systems at various degrees. These ranks are displayed in Table 2. Similarly, for some rainbow parameters over $\mathbb {F}_{16}$, we construct some $\hat{\mathcal {P}}(\textbf{x}) = 0$ systems, and we displayed the ranks of their Macaulay matrices in Table 3. We observe in both cases that the ranks are identical to the ranks of systems of uniformly random quadratic equations with the same dimensions. I.e., if $\tilde{\mathcal {P}}(\textbf{x})$ (or $\hat{\mathcal {P}}(\textbf{x})$) has m equations and n variables, then the rank of its Macaulay matrix at degree D is equal to the coefficient of $t^D$ in the power series expansion of

$$ (1-t)^n (1-(1-t^2)^m) , $$

if this coefficient is positive. Otherwise, the system has a kernel of dimension 1, which corresponds to the 1-dimensional space of solutions. This is evidence that the $\tilde{\mathcal {P}}(\textbf{x}) = 0$ and $\hat{\mathcal {P}}(\textbf{x}) = 0$ systems do not have special properties that make them easier or harder to solve in comparison with random systems.

Combined Attack. Table 4 reports on some of our rank experiments for the combined attack. For some small Rainbow parameter sets, we executed the combined attack from Sect. 4 to derive a MinRank instance with $n-m$ matrices with $n-1$ rows and m columns (of which we keep $m'$). Then we constructed the linearized systems as they appear in the MinRank solving algorithm of Bardet et al. at several bi-degrees (b, 1), and we compute their ranks. We found that in odd characteristic, the rank of the Macaulay matrices always matches those of random MinRank instances with the same parameters. In contrast, we sometimes observe a small rank defect in characteristic two (they are underlined in the Table 4).

Table 2. The rank and the number of columns of the Macaulay matrices for the $\tilde{\mathcal {P}}(\textbf{x}) = 0$ system of equations of simple attack over $\mathbb {F}_{31}$. Ranks of the Macaulay matrix of degree D is given in boldface if the system can be solved at that degree.

Table 3. The rank and the number of columns of the Macaulay matrices for the $\hat{\mathcal {P}}(\textbf{x}) = 0$ system of equations of simple attack over $\mathbb {F}_{16}$. Ranks of the Macaulay matrix of degree D is given in boldface if the system can be solved at that degree.

Table 4. The rank and the number of columns of the Macaulay matrices for the MinRank problems from the combined attack over $\mathbb {F}_{31}$ and $\mathbb {F}_{16}$. Ranks of the Macaulay matrix at bi-degree (b, 1) is given in boldface if the system can be solved at that bi-degree.