Repost of a mathematics stackexchange question here as this concerns my research and it went unanswered on there.
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 because $\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.
