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 . A multivariate quadratic (MQ) is a polynomial in variables where each term’s degree is at most two. For example, a -variable quadratic looks like this: A multivariate quadratic map is a collection of such quadratics where represents sending
Given arbitrary and , finding a solution 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 (the public key) along with a trapdoor (the private key). Then to sign a message, we hash it to a vector and sample a preimage so that .
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 with quadratics of the form Notice that is linear in , since each term contains at most one such variable. To solve , randomly fix and solve the resulting linear equations for . If there is no solution, try again with new random values.
In UOV, we obfuscate an easy-to-invert by composing with an invertible linear map . The public key is , and the private key is the decomposition. We sign by solving and publishing .
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 variables in two phases. Choose , and consider with quadratics of the form To solve , randomly fix . The latter quadratics become linear, and we solve for . This makes the first quadratics linear, and we solve for . Again, we compose with an invertible linear map to obtain .
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 , which implies Analogously, the polar form of is defined to be 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 , the trapdoor is a linear subspace of dimension such that vanishes on , i.e., for all . To sample a preimage for , fix a random vector and find a solution for This equation is linear since is bilinear, is constant, and crucially for any choice of . Intuitively, behaves linearly when restricted to the coset . Since has dimension , we will likely find a solution; otherwise, try again with new . It’s also worth noting that fixing any vector in the coset yields the same solution.
How does this relate to the original description? Consider the easy-to-invert . The trapdoor is the set of vectors whose last entries are zero, i.e. . Fixing the last entries of corresponds with fixing (in particular, the coset element whose first entries are all zero). Solving for the first entries of corresponds with solving for . One can verify the polar equation simplifies into the linear system we solve in UOV. Finally, any trapdoor for translates into a trapdoor in by application of . The UOV signing algorithm is really just solving the polar equation for , rather than directly!
The alternate description of Rainbow follows the same pattern. Again, consider the easy-to-invert . Although our vanishing subspace only has dimension , we do have a subspace of dimension . For any , sends to a vector whose last entries are zero. In other words, is a vanishing subspace if we work in the quotient space , where is spanned by the first standard basis vectors in .
To sample a preimage for , fix a random vector . We use the same technique as in UOV to obtain such that the cosets and are equal. Next, we would like to find a solution for We have chosen so that lies in . We claim that for any choice of , does as well. If this is the case, this constitutes a system of equations and we can expect to find a solution.
To prove the claim, take arbitrary and . The idea is and will only ever vary in the first entries. This is because the last quadratics of ignore the first variables. Hence lies in .
Once is composed with , we obtain secret subspaces , , and .
Now that we’ve come this far, the attack is pretty simple to explain. In Rainbow, for all the differential maps into , which share the same dimension. With its domain restricted to , it behaves like a random linear map (over the choice of ). Hence the probability that is singular, i.e. has a kernel vector in , is approximately . When this happens, the rank- linear system and the -variable quadratic system have a nontrivial intersection, namely a vector in . Finding it amounts to solving an -variable quadratic system. In conjunction with existing key-recovery attacks, this severely weakens Rainbow’s concrete security.
Note that in UOV, sends to a random subspace in . The attack does not apply since the map will almost always be injective.