Multivariate cryptography - easily invertible quadratic map

Question

I am reading through multivariate cryptography and in every source I have seen, the secret map $P$ is described as "easily invertible" or "easy to invert".

What exactly does it mean "easily invertible"?

Answer 1

Normally a multivariate scheme has a central private polynomial map that transforms linear multivariate polynomials into non-linear multivariate polys. This map has to be (easily) invertible, this is, it must allow the owner of the map to recover the original input linear polynomials.

Then define the composition of maps found in a scheme based on MPKC as following:

$$P(p_1(x_1,\ldots,x_n),\ldots, p_n(x_1,\ldots,x_n)) = T \circ \mathcal{F} \circ S(x_1,\ldots,x_n) $$

Or in a simplified version where $X$ denotes the $n$ variables on $x$ and $\varphi : \mathbb{F_p^n} \to \mathbb{F_{p^n}}$:

$$P(p_1(X),\ldots, p_n(X) )= P(X) = T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S(X) $$

As you may know, the public key $P$ consists of $n$ multivariate non-linear polys so when Bob substitutes for $x$ and sends the output $Y$ of $P$ to Alice, she inverts the composition of maps, then:

$$P^{-1}(p_1(X),\ldots, p_n(X) )=P^{-1}(Y) =S^{-1} \circ \varphi^{-1} \circ \mathcal{F}^{-1} \circ \varphi \circ T^{-1}(Y) $$

Obviously, both transormation matrices $T,S \in F_q^{n\times n}$ must be invertible , and the central private polynomial map must be too in some way (trapdoor or root-finding over $\mathbb{F_q}$), recovering the initial values for $X=(x_1,\ldots,x_n)$ that Bob had chosen.

I recommend you to check the Matsuomoto-Imai MV-scheme since it uses the Frobenious Automorphism over $F_2$. There you can learn the insight behind this kind of schemes and procceed to the original version of HFE wich uses the principles of Mat-Imai.