First, affine transformations $S,T$ are defined by $S=A_1+v_s, T=A_2+v_t$. Let the private polynomial function $\mathcal{F}$ be known. The short description of the public key map is $P(X) = T \circ \mathcal{F} \circ S(X)$. Recall that common multivariate schemes are based on the security assumption of IP2, this is, the Isomorphism Of Polynomials with two secrets.

It results that only applying transformations $T$ and $S=I_n$ (the identity) makes the scheme vulnerable by linear algebra attacks. We can recover the transformation matrix $T$ since we already know that it transformed $\mathcal{F}$ to the public key matrix.

In addition, using $T=I_n$ and $S$ an arbitrary invertible affine function, the problem now is equivalent to IP1, which can be stated from the so called Polynomial Affine Equivalence problem (PAE) (see [1] section $2.3$ and $3$). Given $\mathcal{F}(x)$ and $\mathcal{F}(S(x))$ find $S$. Schemes based on IP1 can be vulnerable to attacks if not designed with care, see [2].

Then we are restricted to IP2 if we want to mantain security from this point. Recall that including abritrary invertible affine transformations $S,T$ would make the input-output of $\mathcal{F}$ unknown, even knowing $\mathcal{F}$. Then as $T$ transforms an unknown input, we learn nothing from here nor from the view of PAE or IP1, as we only know one set of quadratic equations $B$ but the set $A$ remains hidden by the transformation $T$.

In the previous description I tried to demonstrate that the knowledge of the private polynomial $\mathcal{F}$ has no effect when the scheme is based on the assumptions of IP2.

However, is there any complication if the private polynomial $\mathcal{F}$ is publicly known from other perspective?

My intiution says that recovering $T$ is fatal as $\mathcal{F}(X), \mathcal{F^{-1}}(X)$ are known the attacker obtains $F^{-1}(Y)=S(X)$. Then to solve IP1 he must establish an affine equivalence function $S$ between $\mathcal{F}(X)$ and $\mathcal{F}(S(X))$

If the attacker doesn't possess $\mathcal{F}$ knowing $T$ will yield $F \circ S(X)$ but yet he doesn't know $\mathcal{F}(X)$, thus IP1 cannot be followed from here.


1 Answer 1


Let's answer my question after revisiting the research. Start by quoting the following text from [2]. Note that I've changed the variables names to fit my description. Here $P(X) = T \circ F \circ S(X)$.

An open question is to know whether or not these schemes remain secure if the set of polynomials $\mathcal{F}$ is public. In this situation, the security of these schemes relies not only on the difficulty of finding a common zero of a system of non linear equations but also on the difficulty of $\mathcal{IP}$ (Isomorphism of Polynomials) problem (when $\mathcal{F}$ and $\mathcal{P}$ are given, the problem is to recover the pairs $(A_1,v_s)$ and $(A_2,v_t)$).

In this post the private polynomial $\mathcal{F}$ is public, moreover described methods reduce IP2 to IP1 if $T$ is known, and IP1 is totally insecure [2]. In the other hand, if $S$ is known $T$ is recovered by basic linear algebra.

Then I conclude that a cryptosystem where $\mathcal{F}$ is known depends on the IP2 assumption (finding $(S,T))$ and the $\mathcal{MQ}$ problem implicitly. You can follow up from [2] section $6.2$

EDIT: Moreover, it results that IP1 is totally broken when the private polynomial is known. However if the polynomial $\mathcal{F}$ is unknown, having access to an oracle then querying for canonical vectors as a plaintext will reveal $S$ too. A secure cryptosystem based on MPKC must satisfy the IP2 assumption from design, between others.


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.