In this paper, Ward Beullens gives another way to look at the Rainbow cryptosystem. In it, he describes the Rainbow map $\mathcal{P}:\mathbb{F}_q^n\to\mathbb{F}_q^m$ with two layers in the following diagram:
In other words, we have:
- $\mathcal{P}(\mathbf{x})\in W$ for all $\mathbf{x}\in O_1$.
- $\mathcal{P}(\mathbf{x})=0$ for all $\mathbf{x}\in O_2$.
- $\mathcal{P}'(\mathbf{x},\mathbf{y})\in W$ for all $\mathbf{x}\in \mathbb{F}_q^n$ and all $\mathbf{y}\in O_2$
where $\mathcal{P}'(\mathbf{x}+\mathbf{y}) = \mathcal{P}(\mathbf{x}+\mathbf{y}) - \mathcal{P}(\mathbf{x}) - \mathcal{P}(\mathbf{y})$ is the differential or polar form of the multivariate system and is a symmetric bilinear form.
Thus $O_2 \subset O_1 \subset \mathbb{F}_q^n$ and $W\subset \mathbb{F}_q^m$. Furthermore, we have $\dim O_2 = \dim W = o_2$ and $\dim O_1 = m$. The "Rainbow trapdoor" is then the knowledge of the subspaces $O_1$, $O_2$ and $W$. Now the author proposes one way of finding a solution to $\mathcal{P}(\mathbf{s})=\mathbf{t}$ if one knows $O_1$, $O_2$ and $W$. The algorithm goes like this:
- First pick uniformly at random a $\mathbf{v}\in\mathbb{F}_q^n$ and solve for $\bar{\mathbf{o}}_1\in O_1/O_2$ such that $$\mathcal{P}(\mathbf{v}+\mathbf{\bar{o}}_1)+W = t + W.$$ Already here I don't understand, $\mathbf{v}$ is in $\mathbb{F}_q^n$ and $\mathbf{\bar{o}}_1$ is in the quotient vector space $O_1/O_2$, how does one add these two elements of different vector spaces? Is there an identification I'm not seeing here?
- In the second part of the algorithm (provided we've found such an $\mathbf{\bar{o}}_1$, we now solve for $\mathbf{o}_2$ in $O_2$ such that $$\mathcal{P}(\mathbf{v}+\mathbf{o}_1 + \mathbf{o}_2) = \mathbf{t}.$$ Again, I don't understand what $\mathbf{o}_1$ represents now. Did we lift the element $\mathbf{\bar{o}}_1$ from the vector space $O_1/O_2$ back into $O_1$? If so, how?
I must admit I'm really confused, any step in the right direction would be well appreciated. This algorithm is given on pages 13-14 in the paper above.