1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

One more thing: it is a good idea to avoid mixing homogeneous quadratic polynomials (i.e., without linear or constant terms) with affine transforms (i.e., with constant terms) -- or vice versa. In other words, whenever your secret polynomials are homogeneous, your secret transforms should be linear; whenever they are inhomogeneous, they should be affine. This guarantees that the public polynomials are (in)homogeneous whenever the secret ones are.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.