# UOV signature scheme, how does the affine transformation work? What does the composition of the core map and the affine map yield?

I am having trouble understanding part of the UOV scheme, i get how it works except for when it comes to composing the core map F with an affine transformation say T, which i understand to be an invertible square matrix? I understand F to be composed of the o number of oil-vinegar polynomials where o is the number of oil variables. So does this mean that each multivariate equation in the core map F is multiplied by a square matrix representing the affine map T? What exactly would be the product of this multiplication? Is each multivariate oil vinegar equation treated as a 1x1 matrix and multiplied with T? I know that the map T is used to do a change of basis on the system but the public key is supposed to be a system of multivariate equations so could someone help clarify what the composition of the core map F and the affine map T actually yields? Perhaps with a small example if possible? For example in the case where o = 2 if i say the core map F is given by

$F = [3x_0^2 - 4x_0x_1 - 4x_1^2 + 8x_0x_2 + 11x_2^2 - 2x_0x_3 - x_1x_3 + 9x_2x_3 + 12x_3^2 + 7x_0x_4 - 11x_1x_4 - 9x_2x_4 - 2x_3x_4 + 3x_0x_5 + 5x_1x_5 + 14x_2x_5 - 11x_3x_5]$

$[-6x_0^2 + 10x_0x_1 + 10x_1^2 + 13x_0x_2 + 4x_1x_2 + 7x_2^2 - 7x_0x_3 - x_1x_3 - 13x_2x_3 + 4x_3^2 + 6x_0x_4 + 15x_1x_4 - 11x_2x_4 - 12x_3x_4 - 12x_0x_5 + 7x_1x_5 - 13x_2x_5 - 9x_3x_5]$

And an affine transformation $T$ given by:

$\begin{bmatrix} 18 & 23 & 14 & 1 & 6 & 21 \\ 24 & 3 & 3 & 0 & 2 & 0 \\ 17 & 25 & 2 & 16 & 23 & 8 \\ 8 & 21 & 16 & 5 & 1 & 9 \\ 14 & 28 & 8 & 17& 12& 12 \\ 6 & 24& 18& 19& 3& 1& \end{bmatrix}$

what would the public key/the composition of the core map F and the map T be?

The secret polynomials are multivariate polynomials whose oil-oil terms have coefficient zero. You can represent it as a sum of terms, or as a vector-matrix-vector product. Take for example the polynomial of your example, $F_0(x_0, \ldots, x_5) = x^2_0 − 4x_0x_1 − 4x^2_1 + 8x_0x_2 + 11x_2^2 − 2x_0x_3 − x_1x_3 + 9x_2x_3 + 12x^2_3 + 7x_0x_4 − 11x_1x_4 − 9x_2x_4 − 2x_3x_4+3x_0x_5+5x_1x_5 + 14x_2x_5 − 11x_3x_5$. Using the vector notation $\mathbf{x}^\mathsf{T} = (x_0, x_1, \ldots, x_5)$ we can write this polynomial as the following product: $$F_0(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix} 1 & -4 & 8 & -2 & 7 & 3 \\ 0 & -4 & 0 & -1 & -11 & 5 \\ 0 & 0 & 0 & 9 & -9 & 14 \\ 0 & 0 & 0 & 12 & -2 & -11 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \right) \mathbf{x} \enspace .$$ The coefficients in the matrix are the same as in the sum-of-terms representation. Note that in this matrix representation, the bottom-right block consists of zeros; this reflects the fact that oil-times-oil terms have coefficient zero. Also note that this matrix is not unique: whenever $F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} M_{F_i} \mathbf{x}$ then for any skew-symmetric matrix $A$ (i.e. such that $A^\mathsf{T} = -A$) you can also write $F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T}(M_{F_i}+A)\mathbf{x}$. In particular, this means that (assuming odd characteristic) it is always possible to choose the central matrix to be symmetric by computing $\frac{1}{2}(M_{F_i}+M_{F_i}^\mathsf{T})$.
The secret linear transform $\mathcal{T}$ can also be represented in two ways. You give the matrix representation $$T = \left( \begin{matrix} 18 & 23 & 14 & 1 & 6 & 21 \\ 24 & 3 & 3 & 0 & 2 & 0 \\ 17 & 25 & 2 & 16 & 23 & 8 \\ 8 & 21 & 16& 5 & 1 & 9 \\ 14 & 28 & 8 & 17 & 12 & 12 \\ 6 & 24 & 18 & 19 & 3 & 1 \end{matrix} \right) \enspace ,$$ in which case $\mathcal{T}(\mathbf{x}) = T\mathbf{x}$. You could also have chosen the list of polynomials representation, in which case there are 6 polynomials, $\mathcal{T}_0$ throught $\mathcal{T}_5$. For illustration, the first polynomial is given by $\mathcal{T}_0(x_0, x_1, x_2, x_3, x_4, x_5) = 18 x_0 + 23 x_1 + 14 x_2 + 1 x_3 + 6 x_4 + 21 x_5$.
To compute the composition $F \circ \mathcal{T}$ you must first choose a representation. In the polynomial representation we have $F \circ \mathcal{T} (\mathbf{x}) = F(\mathcal{T}(\mathbf{x})) = F(\mathcal{T}_0(\mathbf{x}), \mathcal{T}_1(\mathbf{x}), \ldots, \mathcal{T}_5(\mathbf{x}))$. So you can compute $F \circ \mathcal{T}$ by starting with a copy of $F$ and then substituting every occurrence of $x_i$ with $\mathcal{T}(\mathbf{x}) = \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5)$. But make sure to keep track of which occurrences of $x_i$ appear as a result of the substitution, because they obviously shouldn't be substituted twice.
In the matrix representation, we have $F_i \circ \mathcal{T} (\mathbf{x}) = \mathcal{T}(\mathbf{x})^\mathsf{T} M_{F_i} \mathcal{T}(\mathbf{x}) = (T\mathbf{x})^\mathsf{T} M_{F_i} (T \mathbf{x}) = \mathbf{x}^\mathsf{T} (T^\mathsf{T} M_{F_i} T) \mathbf{x}$. So a matrix representation $M_{F_i \circ \mathcal{T}}$ of the composition can be computed just by sandwiching $M_{F_i}$ between $T^\mathsf{T}$ and $T$, i.e., $M_{F_i \circ \mathcal{T}} = T^\mathsf{T} M_{F_i} T$.
To complete the example you started, let's assume we're working modulo 31 (because otherwise the numbers get quite large). Then we have $$M_{F_0 \circ \mathcal{T}} \cong T^\mathsf{T} M_{F_i} T = \left( \begin{matrix} 6 & 25 & 19 & 19 & 3 & 26 \\ 22 & 29 & 3 & 29 & 28 & 2 \\ 8 & 15 & 12 & 18 & 6 & 7 \\ 28 & 1 & 24 & 17 & 4 & 1 \\ 6 & 21 & 18 & 5 & 30 & 23 \\ 11 & 23 & 8 & 15 & 5 & 5 \end{matrix}\right) \cong \left( \begin{matrix} 6 & 8 & 29 & 8 & 20 & 3 \\ 8 & 29 & 9 & 15 & 9 & 28 \\ 29 & 19 & 12 & 21 & 12 & 23 \\ 8 & 15 & 21 & 17 & 20 & 8 \\ 20 & 9 & 12 & 20 & 30 & 14 \\ 3 & 28 & 23 & 8 & 14 & 5 \end{matrix}\right) \cong \left( \begin{matrix} 6 & 16 & 27 & 16 & 9 & 6 \\ 0 & 29 & 18 & 30 & 18 & 25 \\ 0 & 0 & 12 & 11 & 24 & 15 \\ 0 & 0 & 0 & 17 & 9 & 16 \\ 0 & 0 & 0 & 0 & 30 & 28 \\ 0 & 0 & 0 & 0 & 0 & 5 \end{matrix}\right) \enspace .$$ Here the congruence sign ($\cong$) indicates that the matrices represent the same quadratic form, i.e., up to addition of skew-symmetric matrices. In other words, after sandwiching them between $\mathbf{x}^\mathsf{T}$ and $\mathbf{x}$ they will result in the same polynomial. From the last upper triangular matrix we can read out the representation of the polynomial as a sum of terms, namely $$F_0 \circ \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5) = 6x_0^2 + 16x_0x_1 + 27x_0x_2 + 16x_0x_3 + 9x_0x_4 + 6x_0x_5 + 29x_1^2 + 18x_1x_2 + 30x_1x_3 + 18 x_1x_4 + 25x_1x_5 + 12x_2^2 + 11x_2x_3 + 24x_2x_4 + 15x_2x_5 + 17x_3^2 + 9x_3x_4 + 16x_3x_5 + 30x_4^2 + 28x_4x_5 + 5x_5^2 \enspace .$$ This should be the same result as obtained through the substitution method applied to the polynomial representations.