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"?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.