Explaining the Rainbow Attack

February 25, 2022

Yesterday, a practical attack on the Rainbow digital signature scheme (“Breaking Rainbow Takes a Weekend on a Laptop”) was posted on ePrint. Rainbow is a finalist in the NIST post-quantum cryptography competition, which makes this development really exciting! In this post, I want to summarize the attack and provide some additional background for people unfamiliar with multivariate cryptography. In addition to yesterday’s paper, I also referenced this paper.


We will always be working over a finite field Fq\mathbb{F}_q. A multivariate quadratic (MQ) is a polynomial in nn variables where each term’s degree is at most two. For example, a 22-variable quadratic looks like this: f(x1,x2)=α11x12+α12x1x2+α22x22+α1x1+α2x2+α0.f(x_1, x_2) = \alpha_{11} x_1^2 + \alpha_{12} x_1 x_2 + \alpha_{22} x_2^2 + \alpha_1 x_1 + \alpha_2 x_2 + \alpha_0. A multivariate quadratic map F:FqnFqm\mathcal{F}: \mathbb{F}_q^n \to \mathbb{F}_q^m is a collection of mm such quadratics f1,,fmf_1, \dots, f_m where F(x)=y\mathcal{F}(\mathbf{x}) = \mathbf{y} represents sending x=(x1,,xn)toy=(f1(x1,,xn),,fm(x1,,xn)).\mathbf{x} = (x_1, \dots, x_n) \quad \text{to} \quad \mathbf{y} = (f_1(x_1, \dots, x_n), \dots, f_m(x_1, \dots, x_n)).

Given arbitrary F\mathcal{F} and t\mathbf{t}, finding a solution F(s)=t\mathcal{F}(\mathbf{s}) = \mathbf{t} is known to be NP-hard. This suggests that MQ may be a suitable one-way function. For signature schemes, one idea is to engineer a map P\mathcal{P} (the public key) along with a trapdoor (the private key). Then to sign a message, we hash it to a vector t\mathbf{t} and sample a preimage s\mathbf{s} so that P(s)=t\mathcal{P}(\mathbf{s}) = \mathbf{t}.


The unbalanced oil and vinegar (UOV) signature scheme is one of the oldest signature schemes based on MQ. The main observation is that certain multivariate quadratic maps are easy to invert. For example, consider F\mathcal{F} with quadratics of the form f(s)=jk>mαjksjsk.f(\mathbf{s}) = \sum_j \sum_{k > m} \alpha_{jk} s_j s_k. Notice that F\mathcal{F} is linear in s1,,sms_1, \dots, s_m, since each term contains at most one such variable. To solve F(s)=t\mathcal{F}(\mathbf{s}) = \mathbf{t}, randomly fix sm+1,,sns_{m+1}, \dots, s_n and solve the resulting linear equations for s1,,sms_1, \dots, s_m. If there is no solution, try again with new random values.

In UOV, we obfuscate an easy-to-invert F\mathcal{F} by composing with an invertible linear map T\mathcal{T}. The public key is P=FT\mathcal{P}= \mathcal{F}\circ \mathcal{T}, and the private key is the decomposition. We sign t\mathbf{t} by solving F(s)=t\mathcal{F}(\mathbf{s}) = \mathbf{t} and publishing T1(s)\mathcal{T}^{-1}(\mathbf{s}).


Rainbow is a variant of UOV designed to be robust against certain attacks, and therefore have smaller parameters. The idea is to solve for the first mm variables in two phases. Choose 0<o2<m0 < o_2 < m, and consider F\mathcal{F} with quadratics of the form f(s)=jk>o2αjksjskfirst o2 quadratics,f(s)=j>o2k>mαjksjskremaining quadratics.\underbrace{f(\mathbf{s}) = \sum_j \sum_{k > o_2} \alpha_{jk} s_j s_k}_\text{first $o_2$ quadratics}, \quad \underbrace{f(\mathbf{s}) = \sum_{j > o_2} \sum_{k > m} \alpha_{jk} s_j s_k}_\text{remaining quadratics}. To solve F(s)=t\mathcal{F}(\mathbf{s}) = \mathbf{t}, randomly fix sm+1,,sns_{m+1}, \dots, s_n. The latter quadratics become linear, and we solve for so2+1,,sms_{o_2+1}, \dots, s_m. This makes the first o2o_2 quadratics linear, and we solve for s1,,so2s_1, \dots, s_{o_2}. Again, we compose with an invertible linear map to obtain P\mathcal{P}.

Simpler formulations

To better understand the Rainbow attack, we will shift to a conceptually simpler description of the signature schemes. The matrix form of a multivariate quadratic is f(x)=xAx+bx+cf(\mathbf{x}) = \mathbf{x}^\top A \mathbf{x} + \mathbf{b}^\top\mathbf{x} + c, which implies x(A+A)y=f(x+y)f(x)f(y)+c.\mathbf{x}^\top(A + A^\top) \mathbf{y} = f(\mathbf{x} + \mathbf{y}) - f(\mathbf{x}) - f(\mathbf{y}) + c. Analogously, the polar form of F\mathcal{F} is defined to be F(x,y):=F(x+y)F(x)F(y)+F(0),\mathcal{F}'(\mathbf{x}, \mathbf{y}) := \mathcal{F}(\mathbf{x} + \mathbf{y}) - \mathcal{F}(\mathbf{x}) - \mathcal{F}(\mathbf{y}) + \mathcal{F}(0), which is bilinear. From now on we will drop the constant term, which is always zero.


Here is an alternate description of the UOV signature scheme. For a public key P\mathcal{P}, the trapdoor is a linear subspace OFqnO \subset \mathbb{F}_q^n of dimension mm such that P\mathcal{P} vanishes on OO, i.e., P(o)=0\mathcal{P}(\mathbf{o}) = 0 for all oO\mathbf{o} \in O. To sample a preimage for t\mathbf{t}, fix a random vector vFqn\mathbf{v} \in \mathbb{F}_q^n and find a solution oO\mathbf{o} \in O for t=P(v+o)=P(v,o)+P(v)+P(o).\mathbf{t} = \mathcal{P}(\mathbf{v} + \mathbf{o}) = \mathcal{P}'(\mathbf{v}, \mathbf{o}) + \mathcal{P}(\mathbf{v}) + \mathcal{P}(\mathbf{o}). This equation is linear since P\mathcal{P}' is bilinear, P(v)\mathcal{P}(\mathbf{v}) is constant, and crucially P(o)=0\mathcal{P}(\mathbf{o}) = 0 for any choice of o\mathbf{o}. Intuitively, P\mathcal{P} behaves linearly when restricted to the coset v+O\mathbf{v} + O. Since OO has dimension mm, we will likely find a solution; otherwise, try again with new v\mathbf{v}. It’s also worth noting that fixing any vector in the coset v+O\mathbf{v} + O yields the same solution.

How does this relate to the original description? Consider the easy-to-invert F\mathcal{F}. The trapdoor is the set of vectors whose last nmn - m entries are zero, i.e. span{e1,,em}\mathop{\mathrm{span}}\{\mathbf{e}_1, \dots, \mathbf{e}_m\}. Fixing the last nmn - m entries of x\mathbf{x} corresponds with fixing v\mathbf{v} (in particular, the coset element whose first mm entries are all zero). Solving for the first mm entries of x\mathbf{x} corresponds with solving for o\mathbf{o}. One can verify the polar equation simplifies into the linear system we solve in UOV. Finally, any trapdoor for F\mathcal{F} translates into a trapdoor in P\mathcal{P} by application of T1\mathcal{T}^{-1}. The UOV signing algorithm is really just solving the polar equation for F\mathcal{F}, rather than P\mathcal{P} directly!


The alternate description of Rainbow follows the same pattern. Again, consider the easy-to-invert F\mathcal{F}. Although our vanishing subspace O2=span{e1,,eo2}O_2 = \mathop{\mathrm{span}}\{\mathbf{e}_1, \dots, \mathbf{e}_{o_2}\} only has dimension o2o_2, we do have a subspace O1=span{e1,,em}O_1 = \mathop{\mathrm{span}}\{\mathbf{e}_1, \dots, \mathbf{e}_m\} of dimension mm. For any o1O1\mathbf{o}_1 \in O_1, F\mathcal{F} sends o1\mathbf{o}_1 to a vector whose last mo2m - o_2 entries are zero. In other words, O1O_1 is a vanishing subspace if we work in the quotient space Fqm/W\mathbb{F}_q^m / W, where WW is spanned by the first o2o_2 standard basis vectors in Fqm\mathbb{F}_q^m.

To sample a preimage for t\mathbf{t}, fix a random vector vFqn\mathbf{v} \in \mathbb{F}_q^n. We use the same technique as in UOV to obtain o1O1\mathbf{o}_1 \in O_1 such that the cosets F(v+o1)+W\mathcal{F}(\mathbf{v} + \mathbf{o}_1) + W and t+W\mathbf{t} + W are equal. Next, we would like to find a solution o2O2\mathbf{o}_2 \in O_2 for t=F((v+o1)+o2)=F(v+o1,o2)+F(v+o1)+F(o2)=F(v+o1,o2)+F(v+o1).\begin{aligned} t & = \mathcal{F}((\mathbf{v} + \mathbf{o}_1) + \mathbf{o}_2) \\ & = \mathcal{F}'(\mathbf{v} + \mathbf{o}_1, \mathbf{o}_2) + \mathcal{F}(\mathbf{v} + \mathbf{o}_1) + \mathcal{F}(\mathbf{o}_2) \\ & = \mathcal{F}'(\mathbf{v} + \mathbf{o}_1, \mathbf{o}_2) + \mathcal{F}(\mathbf{v} + \mathbf{o}_1). \end{aligned} We have chosen o1\mathbf{o_1} so that F(v+o1)t\mathcal{F}(\mathbf{v} + \mathbf{o}_1) - t lies in WW. We claim that for any choice of o2\mathbf{o}_2, F(v+o1,o2)\mathcal{F}'(\mathbf{v} + \mathbf{o}_1, \mathbf{o}_2) does as well. If this is the case, this constitutes a system of dimW=o2\dim W = o_2 equations and we can expect to find a solution.

To prove the claim, take arbitrary xFqn\mathbf{x} \in \mathbb{F}_q^n and o2O2\mathbf{o}_2 \in O_2. The idea is F(x)\mathcal{F}(\mathbf{x}) and F(x+o2)\mathcal{F}(\mathbf{x} + \mathbf{o}_2) will only ever vary in the first o2o_2 entries. This is because the last mo2m - o_2 quadratics of F\mathcal{F} ignore the first o2o_2 variables. Hence F(x,o2)=F(x+o2)F(x)F(o2)=F(x+o2)F(x)\mathcal{F}'(\mathbf{x}, \mathbf{o}_2) = \mathcal{F}(\mathbf{x} + \mathbf{o}_2) - \mathcal{F}(\mathbf{x}) - \mathcal{F}(\mathbf{o}_2) = \mathcal{F}(\mathbf{x} + \mathbf{o}_2) - \mathcal{F}(\mathbf{x}) lies in WW.

Once T\mathcal{T} is composed with F\mathcal{F}, we obtain secret subspaces O1O_1, O2O_2, and WW.

The attack

Now that we’ve come this far, the attack is pretty simple to explain. In Rainbow, for all xFqn\mathbf{x} \in \mathbb{F}_q^n the differential Dx:FqnFqmyP(x,y)\begin{aligned} D_{\mathbf{x}}: \mathbb{F}_q^n & \to \mathbb{F}_q^m \\ \mathbf{y} & \mapsto \mathcal{P}'(\mathbf{x}, \mathbf{y}) \end{aligned} maps O2O_2 into WW, which share the same dimension. With its domain restricted to O2O_2, it behaves like a random linear map (over the choice of x\mathbf{x}). Hence the probability that DxD_{\mathbf{x}} is singular, i.e. has a kernel vector in O2O_2, is approximately 1/q1/q. When this happens, the rank-mm linear system Dx(o)=0D_{\mathbf{x}}(\mathbf{o}) = 0 and the nn-variable quadratic system P(o)=0\mathcal{P}(\mathbf{o}) = 0 have a nontrivial intersection, namely a vector in O2O_2. Finding it amounts to solving an (nm)(n - m)-variable quadratic system. In conjunction with existing key-recovery attacks, this severely weakens Rainbow’s concrete security.

Note that in UOV, DxD_\mathbf{x} sends OO to a random subspace in Fqm\mathbb{F}_q^m. The attack does not apply since the map will almost always be injective.