Multivariate Cryptography: Security of the affine transform T

Question

In this question, I'd like to discuss the security of the last transformation $T$ employed in the construction of a MV-scheme. MVCrypto is based on solving a system of polynomial equations, but eventually, those polynomials are constructed by a linear combination of $T$ and a vector represententing an univariate polynomial in $F_{q^n}$ with coefficients in $F_q[x_1,\cdots, x_n]$. The following construction illustrates a typical description, where $\alpha : F_{q^n} \mapsto F_{q^n}$ is the transformation function (i:e Matsumoto-Imai) that changes the coefficients of $x'$ that are multivariate linear polynomials to multivariate non-linear polynomials. Note that here $v_s,v_t=[0]_n\in F_q^n$. \begin{equation} S,T \in F_q^{n \times n}, \quad x=(x_1,\dots,x_n)\in F_q^n \\ x'=S\cdot x \\y'=\alpha(x')\\y=T\cdot y' \end{equation}

Matrices are very useful since we can represent $F_{q^n}$ as $F_q^n$: the n-dimensional vector space over $F_q$. So $x'$ can be viewed as a polynomial with coefficients that are linear combinations on $x$.

$$x'= \sum_{i=1}^{n}(\sum_{j=1}^{n} S_{i,j}\cdot x_j)y^{i-1}$$

The attacker has $n$ multivariate polynomials and their evaluation on $x=(x_1,\cdots,x_n)$. If he finds out the transformation $T$, he could attempt to invert $\alpha$ to obtain $x'$ and finally, $x$. My intuition tells me that an attacker can find a pair $z\in F_q^n, T'\in F_q^{n\times n}$ s.t satisfies $T'\cdot z = y$. As an example, consider the following case where $V=F_5^2$:

$T=\left( \begin{array}{cc} 1 & 2 \\ 3 & 1 \\ \end{array} \right)$ $y'=(x_1x_2-1,x_1^2x_2+3)$

$T\cdot y' = y = (x_1x_2+2x_1^2x_2, 3x_1x_2+x_1^2x_2)$

It's pretty straightforward to recover $T'=T$ and $z=(x_1x_2,x_1^2x_2)$ since $y$ contains coefficients that are $n$ sums of the same $n$ factors, here $n=2$. Note that $z\neq y'$ but in this case is not hard to "bruteforce" until reaching the correct one.

---

EDIT: It's important that you note that $S$ and $T$ are interchanged in my example, $S$ is the first affine transformation and $T$ is the last one, however, in literature you found this to be the opposite. So the remark is that this question is about the last transform applied in the construction.

Question: Is there any information that describe an inversion of this construction, not by solving the polynomial eqs. but inverting the maps?

Answer 1

Almost a year since I posted this question, back then I was starting the study of the field. Now I can answer myself:

The security of both affine transforms $(T,S)$ relies on the IP2 assumption defined in the Isomorphism of Polynomials. Plus, if the private polynomial $\mathcal{F}$ is known there are other implications, like finding $T$ or $S$ would reveal the other affine transform.

This is, any multivariate scheme where $F,S$ or $F,T$ is known gives us the ability to break it. When $F$ is not known, as usually, we could obtain $T\cdot S$ as a matrix if both are linear transform instead of affine, and the linear part of $F$ is the identity matrix. From here nothing else can extracted, from the moment, in my study.

Regarding IP1, it can be broken when $F$ is known, or when $F$ is unknown by quering an oracle $n$ times with the canonical vectors $\overrightarrow{e_i}$.

Besides other techniques to strip out $T,S$ exist, i.e: when the characteristic is not $2$ and both transforms are linear.

There is more work not published in literature that I've discovered, i.e: the special structure of matrices $S$ that make the private polynomial invariant in a way that we can revover $T$, and more techniques that the audience must await for.