# Multivariate Cryptography: Security of the affine transform T

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$$. $$$$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'$$$$

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?