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

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.